2018.1 Programação Funcional

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.

Unix tips

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

  • Hutton: Programming in Haskell
  • Bird: Thinking Functionally with Haskell

Papers

Auxiliar

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:

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:

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

  1. Instale a Haskell no teu sistema. Vai precisar instalar o tool stack. Siga as instruções nos sites.
  2. 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.
  3. Se acostume com o canal IRC de Haskell.
  4. 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).
  5. 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.
  6. Se nunca programou em LISP, comece aprender uma! Sugiro brincar com Racket, e criar suas próprias linguagens de programação!
  7. 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

  1. Estude as secções «Funções de ordem superior» e «Currificação» do capítulo «Funções» do meu livro.
  2. Estude o Capítulo 2 de LYAH.
  3. Estude o Capítulo 2 de Hutton e resolva seus exercícios.

01/03/2018

  1. Estude os Capítulos 3 e 4 de LYAH.
  2. Estude os Capítulos 3 e 4 de Hutton e resolva seus exercícios.
  3. Estude os Capítulos 3 e 4 do HaskellBook e resolva seus exercícios.

10/03/2018

  1. Estude o Capítulo 5 de Hutton e resolva seus exercícios.

12/03/2018

  1. Defina todos os undefined no ExNat.hs

19/03/2018

  1. Defina todos os undefined no ExComb.hs
  2. Estude o Capítulo 5 de Hutton e resolva seus exercícios!

22/03/2018

  1. Defina todos os undefined no ExRat.hs.
  2. Defina todos os undefined no ExComplex.hs.
  3. Defina todos os undefined no ExMatrix2x2.hs.
  4. Generalize o ExMatrix2x2 para um ExMatrix.
  5. Ache defeitos nas abordagens de todos esses modules.

27/03/2018

  1. Estude o Capítulo 5 de LYAH.
  2. Estude o Capítulo 6 de Hutton e resolva seus exercícios.

28/03/2018

  1. Resolva todo o ExList.hs. (Copie ele novamente no teu homedir, pois já mudei várias coisas!)

02/04/2018

  1. TERMINEM TODOS OS HOMEWORKS PENDENTES!
  2. Estude o MySort.hs
  3. Estude o (atualizado hoje) ExList.hs
  4. O (++) é realmente associativo?
  5. Teu (+) é associativo no teu Nat?
  6. Declare uma boa associatividade e precedência nos operadores dos teus modules até agora.

05/04/2018

  1. Resolva o Drunk.hs
  2. Estude e brinque com o JPHalve.hs

18/04/2018

  1. TERMINEM TODOS OS HOMEWORKS PENDENTES! (Especialmente o Nat e o List.)
  2. Redefina (sem olhar) a permutations definindo e usando a interpose
  3. Defina a permutations definindo e usando a insertAt

24/04/2018

  1. Verifique todos os leis que encontramos nas aulas
  2. 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

  1. Prove tudo que está na secção «Provando propriedades de operações e relações nos naturais» no capítulo «Indução» do fmcbook
  2. 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

  1. sum (xs ++ ys) = sum xs + sum ys
  2. concat (xss ++ yss) = concat xss ++ concat yss
  3. filter p (xs ++ ys) = filter p xs ++ filter p ys
  4. map f (xs ++ ys) = map f xs ++ map f ys
  5. sum (reverse xs) = sum xs
  6. length (reverse xs) = length xs
  7. w `elem` (xs ++ ys) = w `elem` xs || w `elem` ys
  8. zip (fst (unzip ps)) (snd (unzip ps)) = ps
  9. take n xs ++ drop n xs =?= xs
  10. head . map f =?= f . head
  11. map id = id
  12. map (g . h) = map g . map h
  13. Verifique todas essas propriedades com QuickCheck

28/05/2018

  1. Defina as funções seguintes usando fold:
  2. Defina todos os undefined no ExFold.hs
  3. 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?
  4. Defina a adição (binária) e o somatório (unário, recebendo lista) para Maybe Integers.
  5. Defina o countsF do DbObjects.hs
  6. Defina todos os undefined no ExMaybe.hs
  7. Defina todos os undefined no ExEither.hs

31/05/2018

  1. Defina todos os undefined no ExIO.hs (tu vai precisar saber como read)

06/06/2018 – 07/06/2018

  1. TERMINEM TODOS OS HOMEWORKS PENDENTES! (Especialmente os: ExMaybe; ExEither; ExIO)
  2. Estudem o paper de Hutton que tá na bibliografia

14/06/2018

  1. 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 de double (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 vs data
  • 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 geral List α
  • :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 MonadPlus
  • data Wrapper a = Wrap a
  • bind não pode ser definido pelas fmap, 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!

Last update: Tue Jul 10 09:37:08 -03 2018