Horários: | 24T56 [16h50–18h30] |
Sala de aulas: | A304 (2T56) & A103 (4T56) |
Sala do prof: | A225 |
Contato: | thanos@imd.ufrn.br |
Horário de atendimento: | mande email para marcar |
Uso do servidor: | tips |
Prerequisitos
- Óbvios:
- {vontade, tempo} para {hackear, praticar, procurar, implementar, programar} nos assuntos da disciplina;
- fluência em pelo menos um dos dois editores de texto que prestam (Vim & Emacs) ajuda em qualquer tarefa que envolve criação de arquivos de texto.
- Experiência com programação não-funcional (disfuncional) atrapalharia mas NÃO será estritamente proibida. ;)
- Nada mais!
Para o lado prático da disciplina e seus trabalhos, vamos precisar as noções básicas de Unix e familiaridade com git.
Conteúdo
Conceitos de programação funcional, introdução ao lambda calculus, o modelo de computação de programação funcional, tipos de dados, recursão, programação de ordem superior, evaluação preguiçosa, dados infinitos, I/O, classes de tipos, monads, raciocinando sobre programas, indução, parseando, programação paralela e concorrente, programação com tipos dependentes.
Bibliografia
Principal
(Conhece o libgen.io?)
- Programming in Haskell :
- Thinking Functionally with Haskell :
Papers
Auxiliar
- Learn you a Haskell for great good (LYAH) :
- Real World Haskell :
- Typeclassopedia :
- What I wish I knew when learning Haskell :
- The Craft of Functional Programming :
- Introduction to Functional Programming using Haskell :
- The Haskell Road to Logic, Maths and Programming :
- The Little Schemer :
- Pearls of Functional Algorithm Design :
- Parallel and Concurrent Programming in Haskell :
- Developing Web Applications with Haskell and Yesod :
- PureScript by Example :
- Type-driven development with Idris :
- The Algebra of Programming :
- Software Foundations :
- Matemática Fundacional para Computação :
Links
Haskell ; Idris ; PureScript ; Neovim ; Emacs
Live Coding
32 participantes: aaar2 akandor allanrego binaks carlos ericdsm ggorg03 giordanorn italogomes itepifanio jaimerson joelffg jomedeiros jp jplinha jsneto louise lpgoulart macielbarbosa matheusanmo mazuh mrmorais natalia089 paulossm sarah vash victoroliveira viniciuscampos vitorgreati welligton wgordo xprime
Provas
Material para ajudar na preparação para a prova
Isso não quis dizer que na prova vão cair (apenas) problemas desses assuntos
- Homework modules: ExNat, ExList, ExMaybe, ExEither, ExFold, MySort
- Hutton: 5, 6, 7, 16
- Bird: 3, 4, 6
- fmcbook: o capítulo «Os números naturais: recursão; indução»
Prova U2
- Prova (única) escrita (pts: 126; bonus: 0) (dia: 02/07/2018)
{ uncensored }
Prova de Reposição
- Prova 4 (pts: 124; bonus: 0) (dia: 09/07/2018)
{ uncensored }
Projeto
O projeto vai ter que ser desenvolvido no servidor, e compilado para criar um binário, executável na máquina mesmo.
Veja os tutoriais seguintes:
- Stack on piffy (haskell.imd.ufrn.br)
- How to Play with Stack
- How to Script with Stack
- How to Build with Stack
- How I start: project in Haskell
Estude o capítulo 15 de Thompson.
O RWH é muito antigo (dated) para seguir seus exemplos fielmente, mas suas idéias para programar no mundo real são aplicáveis, e o fato que tem comentários de leitores em cada parágrafo ajuda demais.
Tristeza com strings:
- A Sticky Stringy Quandary
- Fácil para usar: Data.String.Conversions
Pontos extra
Unidade 1
JP | 25 |
Joel Felipe | 10 |
Natália | 15 |
Josivan | 11 |
Louise | 14 |
Bianca | 12 |
JP' | 10 |
Miguel | 3 |
Matheus | 15 |
Sarah | 12 |
x' | 9 |
Vinícius | 10 |
Vitor | 14 |
Gustavo | 7 |
Gabriel | 2 |
Jaimerson | 3 |
Arthur | 4 |
Fernando Igor | 5 |
Homework
Os arquivos existem no servidor no ~/funfiles
.
Olhem com freqüência para possíveis modificações/correções!
19/02/2018
- Instale a Haskell no teu sistema. Vai precisar instalar o tool stack. Siga as instruções nos sites.
- Aprenda os básicos de pelo menos um dos dois editores que prestam:
- para o (neo)vim, complete seu tutorial: execute o
vimtutor
- para o Emacs, complete seu tutorial: execute o
emacs
, e siga as instruções para entrar no tutorial.
- para o (neo)vim, complete seu tutorial: execute o
- Se acostume com o canal IRC de Haskell.
- Especialmente se tu programa em Java, dê uma olhada em Scala. Vale a pena assistir os primeiros minutos dessa palestra (especialmente os exemplos com o código que começa no tempo 8m45s).
- Especialmente se tu já programou em JavaScript, dê uma olhada na Elm. Tente modificar esse exemplo, para adicionar um feature nele, mesmo sem ter visto Elm nunca antes. Por exemplo, tente adicionar um botão Reset que zera esse contador. Compare essa solução com o jeito que tu faria isso em JavaScript pura.
- Se nunca programou em LISP, comece aprender uma! Sugiro brincar com Racket, e criar suas próprias linguagens de programação!
- Comece estudar o LYAH (veja na bibliografia).
(Obs: não vamos usar nenhuma LISP, nem Scala, nem Elm nessa disciplina! É só pra tua diversão mesmo.)
26/02/2018
- Estude as secções «Funções de ordem superior» e «Currificação» do capítulo «Funções» do meu livro.
- Estude o Capítulo 2 de LYAH.
- Estude o Capítulo 2 de Hutton e resolva seus exercícios.
01/03/2018
- Estude os Capítulos 3 e 4 de LYAH.
- Estude os Capítulos 3 e 4 de Hutton e resolva seus exercícios.
- Estude os Capítulos 3 e 4 do HaskellBook e resolva seus exercícios.
10/03/2018
- Estude o Capítulo 5 de Hutton e resolva seus exercícios.
12/03/2018
- Defina todos os undefined no ExNat.hs
19/03/2018
- Defina todos os undefined no ExComb.hs
- Estude o Capítulo 5 de Hutton e resolva seus exercícios!
22/03/2018
- Defina todos os undefined no ExRat.hs.
- Defina todos os undefined no ExComplex.hs.
- Defina todos os undefined no ExMatrix2x2.hs.
- Generalize o ExMatrix2x2 para um ExMatrix.
- Ache defeitos nas abordagens de todos esses modules.
27/03/2018
- Estude o Capítulo 5 de LYAH.
- Estude o Capítulo 6 de Hutton e resolva seus exercícios.
28/03/2018
- Resolva todo o ExList.hs. (Copie ele novamente no teu homedir, pois já mudei várias coisas!)
02/04/2018
- TERMINEM TODOS OS HOMEWORKS PENDENTES!
- Estude o MySort.hs
- Estude o (atualizado hoje) ExList.hs
- O (++) é realmente associativo?
- Teu (+) é associativo no teu Nat?
- Declare uma boa associatividade e precedência nos operadores dos teus modules até agora.
05/04/2018
- Resolva o Drunk.hs
- Estude e brinque com o JPHalve.hs
18/04/2018
- TERMINEM TODOS OS HOMEWORKS PENDENTES! (Especialmente o Nat e o List.)
- Redefina (sem olhar) a permutations definindo e usando a interpose
- Defina a permutations definindo e usando a insertAt
24/04/2018
- Verifique todos os leis que encontramos nas aulas
-
Define unzip and cross by:
unzip = pair (map fst,map snd) cross (f,g) = pair (f . fst,g . snd)
Prove that:cross (map f, map g) . unzip = unzip . map (cross (f,g)) cross (f,g) . cross (h,k) = cross (f . h,g . k)
25/04/2018 – 03/05/2018
- Prove tudo que está na secção «Provando propriedades de operações e relações nos naturais» no capítulo «Indução» do fmcbook
- Defina uma seqüência de funções funn tais que as add, mul, e exp, são apenas uns dos seus termos. Implementa a fun do ExFun.hs
07/05/2018
- sum (xs ++ ys) = sum xs + sum ys
- concat (xss ++ yss) = concat xss ++ concat yss
- filter p (xs ++ ys) = filter p xs ++ filter p ys
- map f (xs ++ ys) = map f xs ++ map f ys
- sum (reverse xs) = sum xs
- length (reverse xs) = length xs
- w `elem` (xs ++ ys) = w `elem` xs || w `elem` ys
- zip (fst (unzip ps)) (snd (unzip ps)) = ps
- take n xs ++ drop n xs =?= xs
- head . map f =?= f . head
- map id = id
- map (g . h) = map g . map h
- Verifique todas essas propriedades com QuickCheck
28/05/2018
- Defina as funções seguintes usando fold:
- Defina todos os undefined no ExFold.hs
- Defina uma função emap, para comportar como a map, mas em vez de listas, em eithers: qual seria um tipo razoável para a emap?
- Defina a adição (binária) e o somatório (unário, recebendo lista) para Maybe Integers.
- Defina o countsF do DbObjects.hs
- Defina todos os undefined no ExMaybe.hs
- Defina todos os undefined no ExEither.hs
31/05/2018
06/06/2018 – 07/06/2018
- TERMINEM TODOS OS HOMEWORKS PENDENTES! (Especialmente os: ExMaybe; ExEither; ExIO)
- Estudem o paper de Hutton que tá na bibliografia
14/06/2018
- Desenvolva projetos pequenos! Por exemplo joguinhos como o hangman.
Vale a pena brincar com os módulos seguintes:Data.Functor Data.List Data.Char Data.Set Data.Maybe Data.Either Data.Time Control.Applicative Control.Monad Text.Printf System.IO System.Random System.Environment System.Directory System.Console.ANSI System.Process
Histórico de aulas
19/02/2018: Apresentação
- Apresentação dos assuntos principais
- Paradigmas de linguagens de programação
- Imperativo; Declarativo
- Programação funcional e programação lógica
- Funções vs Relações
- A família LISP
- Lazy evaluation
21/02/2018
- Estratégias da evaluação
- Dois teoremas sobre estratégia de evaluação
x = 2
em Haskell vs. outras linguagens- Programa como dicçionário de definições
- A ordem de definições não importa
- A ordem de equações (duma definição) importa
- Tipos
- Listas
- Açucar sintáctico
- if then else
- Lazy vs. Strict
- Infinidade
- Uma multiplicação mais esperta
- Um
double
estranho e o valor dedouble (double 1)
- Inferença de tipos
- Tuplas vs. Listas
26/02/2018
- it (GHCi)
- comentários
- precedência de aplicação
- umas funções de Prelude: head; tail; take; drop; sin; cos; sqrt
- sin(x) vs. sin
- abstraindo com buracos em expressões
- First-class; Higher-order functions
- λ-calculus
- λx.f(x) = f
- currificação: curry, uncurry
- aplicação parcial
28/02/2018
- λ-calculus recap
- β-redex; β-redução
- α, η equivalências
- where
- pattern-matching
- nomes com símbolos: + vs. (+)
- polymorphic types
- fst; snd
- unicidade de programa dado tipos: (a,b) → a; (a,b) → b; a → a
- inferência de tipos
- a → b → c → d vs. a → (b → (c → d))
05/03/2018
- side effects e "hello world"
- umas funcionalidades de tipos
- tipos primitivos
- tipos compostos (por [–], (–,–), –→–, etc.)
- abuso de tipos («bota lá um -1 e pronto»)
- infix/prefix: (+), `mod`, `elem`, etc.
- nomes válidos para funções, tipos, valores
- defining new data types
- um tipo
Weekday
- guards
- erro no ghci: «não sei como show'ar esse valor pra ti»
- erro ná compilação: «não sei o que significa igualdade para esse tipo de coisa»
deriving (Eq, Show)
- MyBool.hs
07/03/2018
- data Bool e suas funções
- nomes em Haskell: começando com minúsculo vs. maiúsculo
- nomes para operadores (feitos por símbolos)
- precedências: função aplicação (f x) vs. (f $ x)
- secções e aplicação parcial
- (+ 2), (3 *), (< 8), (`mod` 2), e seus tipos
- (,) (,,) (,,,) e seus tipos
- listas
- head; tail; init; last
- length; reverse; e seus tipos
- even; odd
- map; filter;
- take; drop; takeWhile; dropWhile
- (:) e seu tipo
- Nata.hs
12/03/2018
- o mundo de tipos vs. o mundo de valores
- o valor ⊥ (bottom)
foo x y = algo x y
vs.foo x = algo x
vs.foo = algo
- composição
- flip
- o tipo
Nat
- Definindo nossas próprias instances
Show Nat
Eq Nat
:type Succ
;:type Succ Zero
- MyFlip.hs
14/03/2018: Nats & bottoms
- Sobre o Nat.hs.
- aplicação denotada por “ ” vs. por “
$
” - Typeclasses & Constraints
- Ord
- Enum
:info
- Satisfazendo as typeclasses Integral, Real, Num
- Composição revisitada
- definições pointless (point-free) vs pointfull
- Construtores de valores: Succ vs. succ
- O mundo de tipos vs. o mundo de valores
:type
vs.:kind
- Convenções de Haskell: nómes começando com minúsculo vs. maiúsculo
- max; min; maximum; minimum
- Todos os valores do tipo Bool
- bottom e suas propriedades
- Os números parciais
- Todos os valores do tipo Nat
- atLeast :: Integer → Nat
- O número infinito: infinity = Succ infinity
- Como provar que o infinity não tem um valor nem de número natural nem de número parcial
- Max3.hs
19/03/2018: Modules; Testing; Lists
- literate programming
- rational numbers
- modules, imports, encapsulamento
- Data.Char; Data.List
- :browse & :info
- Ordering
- precedência de operadores:
infixl
/infixr
- testing: Test.QuickCheck
- sort
- sum; product; concat
- zip; zipWith; all; any
- repeat
- List comprehension
- quadratic roots; sqrt
- Quad.hs
- Testing com aritmética flutuante
- let-expressions
- let vs where
21/03/2018
- GHC Extensions: PostfixOperators; UnicodeSyntax
- PairIntInt; PairIntBool; TripleBoolIntBool; etc.
- MkPairIntInt; MkPairIntBook; MkTripleBoolIntBool; etc.
- data Person = Amigo String | Colega String String
- Pair a b; MkPair a b;
- Construtores de valores vs. construtores de typos
- (), (,), (,,), etc. nos dois mundos
- sinónimos de tipos:
type
type
vsdata
- Rat.hs
26/03/2018: Listas
- Pattern matching com
case ... of ...
- Como implementar o tipo
ListInt
de «lista de inteiros» - Construtores com símbolos começam com
:
- Operadores infixos: suas associatividades e precedências
- Do tipo
ListInt
para o tipo geralList α
:kind []
vs.:type []
- Recursão nas listas
- As funções: head; tail; null; length; sum; product; reverse; take; drop; takeWhile; dropWhile
- a diferença entre length e sum
- TakeDrop.hs
28/03/2018: Listas
- Construtores vs. Destrutores
- Pattern-matching com
where
- Eficiência
- subtract e secções
- sumLastThree; sumLast
- definição por composição
- Duas definições de (++)
- snoc
- MMT.hs
02/04/2018: Listas
- Reimplementação do algoritmo de Matheus para a sumLastThree
- Todas as equações tem que compartilhar o mesmo número de argumentos
- As funções: elem; (!!); map; filter; splitAt
- Eficiência: associatividade esquerda ou direta? (++)
- Dois jeitos diferentes para pensar sobre a map: função de aridade 1 vs. função de aridade 2
- Eficiência: duas definições de splitAt
- Sorting
- merge sort
- insertion sort
- Mirror.hs
04/04/2018: Listas
- Sorting de novo
- Quick sort
- as-patterns
- GADTs extension
- halve primitivo (sem splitAt)
- Drunk.hs
09/04/2018
- Idéias sobre a implementação de Matrix2x2 e de Matrix
- As funções: lines; split; drunk; alternate; until; iterate; collatz
- Generalizações de problemas
- Mais uma implementação da until
- Mais sobre as-patterns
- A conjectura Collatz
- merge & sorted: como testar
- Mais testing com QuickCheck
- O operador
==>
- Aqui.hs
11/04/2018
- Mais testing com QuickCheck
- Defeitos nos modules dos homeworks
- Nomeação consistente
- zip usando zipWith
- cycle usando repeat
- ones
- As funções: iterate; and; or; all; any; isPrefixOf; zip; zipWith; unzip; subsequences; inits; tails
- MoreLists.hs
16/04/2018
- Revisão: map, filter, zip, zipWith, unzip, concat, inits, tails, subsequences, length, curry, uncurry, flip, (+), (*), (^), Nat, List α
- Definindo listas recursivamente
- ones, nats, fibs
- Equational reasoning
- Diagramas comutativos
- cross; pair
- Umas leis de take, drop, map, cross, pair
- ER.hs
18/04/2018
- ListR.hs
- inits; tails; subsequences; rotate
- permutations usando interpose
- Hoogλe
23/04/2018
- CP.hs
- funções:
- inserts;
- insertAt;
- inserts (usando insertAt);
- cp (produto cartesiano);
- leis:
take n xs ++ drop n xs = xs take m . drop n = drop n . take (m + n) take m . take n = take (m `min` n) drop m . drop n = drop (m + n) map g . map f = map (g . f) cross (f,g) . pair (h,k) = pair (f . h,g . k) pair (f,g) . h = pair (f . h,g . h) fst . cross (f,g) = f . fst snd . cross (f,g) = g . snd cross (f,g) . cross (h,k) = cross (f . h,g . k) sum . map double = double . sum (distr.) sum . map sum = sum . concat (assoc.) sum . sort = sum (commut.) map f . reverse = reverse . map f concat . map concat = concat . concat filter p . map f = map f . filter (p . f)
25/04/2018
- Partition.hs
- Mais equational reasoning
- Substituição bidirecional (provas matemáticas) vs. unidirecional (computação Haskell)
- Aplicando e desaplicando definições
- Cuidado com overlapping patterns
- Predicados de várias aridades
- Técnicas de provas
- Indução nos naturais
30/04/2018
- Induction.hs
- Provas por indução em todo detalhe
- A adição é associativa
- A adição é comutativa
02/05/2018
- Induction2.hs
- Provas por indução em todo detalhe
- A multiplicação é associativa
- A multiplicação é comutativa
- Distributividade pela esquerda
- Distributividade pela direita
- O princípio da indução para listas
07/05/2018
- Linduction.hs
- Lei da exponenciação 1
- Lei da exponenciação 2
- O princípio da indução para listas finitas
- sum (doubleAll xs) = 2 * sum xs
- rev (xs ++ ys) = rev ys ++ rev xs
- rev . rev = id
- (++) é associativa
- length (xs ++ ys) = length xs + length ys
09/05/2018: Aula cancelada
14/05/2018: Aula cancelada
16/05/2018: Aula cancelada
21/05/2018
- Funções strict
- Eficiência do reverse
- Usando prova por indução para achar definição eficiente
- Listas Nonempty
- Arvores com valores em nodes e leaves
- Arvores com valores apenas nos leaves
- Trees.hs
- flatten & tmap
23/05/2018
- Maybe α
- Either α β
- foldr
- FF.hs
28/05/2018
- Record syntax
- Smart constructors
- even better with type synonyms
- even better with Maybe Person
- even better with Either String Person
- even better with Either [String] Person
- even better with Either [PersonError] Person
- May.hs
- mmap: como map mas para Maybes em vez de Listas
- Traversando lista de objetos de um suposto banco de dado: com e sem foldr
- Input/Output em Haskell
- IO α ∷ *
- IO ∷ * → *
- putStrLn, putStr, getLine
- Hello, world!
30/05/2018
- O tipo Unit e seu “único” valór:
()
- Input/Output
- Os typos
IO α
- O que GHCi faz
- Uns primitives de I/O: putChar, getLine, e seus amigos
- O módulo
System.Directory
- A notação
do
e a setinha de atribuição←
- A função
return ∷ α → IO ()
- Funções puras vs. impuras
- Grr.hs
04/06/2018
- Mais input/output
- Os operadores «and then» (≫) e «bind» (≫=)
- O açucar sintáctico da do-notation desaçucarificado
- Construindo uma linguagem imperativa
- IO1.hs
- Resolução (parcial) do homework ExIO (botei o arquivo na pasta funfiles como IOkit.hs)
06/06/2018
- Interpretação computacional de lista, maybe, either, IO.
- Última continuação do homework ExIO (atualizei o arquivo na pasta funfiles como IOkit.hs)
- IO2.hs
11/06/2018
- thunks
:sprint
(GHCi)- _holes
- mais sobre a do-notation
- Functors
- VO.hs
13/06/2018
- do-notation desugaring
- Strictness of do stmts
cheat :: IO α → α
- Explicação de todo o ExIO
- Functors; Applicative; Monads
- do-notation for non-IO monads
18/06/2018
- A hierarquia Functor–Applicative–Monad
- Functor
- Definições obrigatórias
- Definições de graçá
- A ideia do fmap:
fmap
&<$>
- Leis
- Functors: Maybe, List, IO
- Applicative
- Definições obrigatórias
- Definições de graçá
- A ideia do «splat»:
<*>
- Leis
- Leis de Applicative como rewrite rules para chegar na applicative form:
[[g x1 x2 ... xn]]
- Applicatives: Maybe, List, IO
- A hierarquia Semigroup–Monoid–Group–Abelian
20/06/2018
- Either (revisão)
- (Either ε :: * → *) é um functor
- Exemplos de Semigrupos
newtype
vs.data
vs.type
- tipos isómorfos
- Uso de newtype para satisfazer o mesmo typeclass em maneiras diferentes
- Duas maneiras diferentes de definir o List como Applicative
25/06/2018
- De Applicative para Monad
fail
e MonadPlusdata Wrapper a = Wrap a
bind
não pode ser definido pelasfmap
,pure
,<*>
- compilação com ghc
- exemplos de real-life pacotes/bibliotecas: getArgs, scotty, etc.
- Exposição da fold (por Gustavo)
27/06/2018: Aula cancelada
02/07/2018: Prova
04/07/2018: Apresentação de projetos
09/07/2018: Prova de reposição
Futuro (fluido)
Sem futuro: o semestre acabou!