2022.2 FUN: Programação Funcional, turma de Thanos

Pontos de participação

Homework (HW)

• Homeworks são atribuidos também durante as aulas (gravadas) e no Zulip.
• Homeworks marcados assim são auxiliares; tente apenas se tu tem resolvido uma parte satisfatória dos outros.

Pré…

1. 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.
   • caso preferir usar outro editor (por exemplo VSCode), procure ver como adaptá-lo para facilitar o desenvolvimento em Haskell.
2. 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).
3. 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.
4. Se nunca programou em LISP, comece aprender uma! Sugiro brincar com Racket, e criar suas próprias linguagens de programação! Para os Javistas, Clojure seria uma opção boa.
5. 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.)

2022-08-23

1. Instale a Haskell no teu sistema (veja o FAQ relevante), e as ferramentas relevantes (incluindo editor).

2022-08-25

1. Estude a secção «Um toque de lambda» do capítulo «Funções» do fmcbook.
2. Estude os capítulos 3 e 4 do [Hutton]
3. Estude os capítulos 2–4 do LYAH

2022-09-05

1. Defina todos os undefined no ExBool.hs

2022-09-06

1. (Sem roubar) qual é o tipo de error?
2. Complete o RPG.hs
3. Complete o ExNat.hs
4. Complete o ExList.hs
5. Complete o ExRat.hs
6. Complete o ExMatrix2x2.hs
7. Complete o ExComplex.hs
8. Estude o capítulo 5 do LYAH

2022-09-14

1. Estude o capítulo 2 de [Bird]
2. Estude o capítulo 5 de [Hutton]

2022-09-19

1. Estude o capítulo 6 de LYAH
2. Estude o capítulo 7 de [Hutton]
3. Complete o ExFromWhile.hs; defina cada função usando apenas uma curta equação.

2022-09-28

1. Complete o ExMaybe.hs
2. Complete o ExBox.hs
3. Complete o ExBottom.hs

2022-10-07

1. Estude o capítulo 4 de [Bird]

2022-10-17

1. Estude o capítulo 6 de [Hutton]

2022-10-22

1. Estude o capítulo «Funções» do fmcbook até o segundo intervalo de problemas, a §«Definições recursivas».
2. Resolva o ExFirstThat.hs, mas essa vez numa maneira legal.
3. Volte a trabalhar em todos os Ex*.hs, essa vez alerto para programar numa maneira mais legal:
   • melhor caligrafia: indentação, line-breaks, whitespace, parenteses, etc.
   • melhor abstracções
   • elimine equações inúteis
   • elimine repetições usando where e/ou let
   • reduza expressões para equivalentes mais simples
   • use pattern matching em vez de testes com booleanos quando possível
   • tente quebrar teu problema em menores para usar composições
   • elimine “pontos” inúteis de equações—mas não chega a exagerar sacrificando a legibilidade!
4. Resolva o ExSet.hs; estude as primeiras secções do capítulo «conjuntos» do fmcbook caso precise
5. Defina elementariamente uma função halve ∷ [a] → ([a],[a]) para ser usada no merge sort.
6. Resolva o ExEither.hs.
7. Resolva o ExDrunk.hs.
8. Resolva o ExHyper.hs.
9. Defina o sorted com uma equação só, usando o zipWith.

2022-10-27

1. Defina a filter usando a concat.
2. Resolva o ExCommonWords.hs
3. Resolva o Inhabitants.hs

2022-10-28

1. Q: not . elem False ≟ and
2. Resolva o ExUsing.hs
3. Resolva o ExCurry.hs
4. Resolva o ExCH.hs
5. Resolva o ExArith.hs
6. Resolva o ExVArith.hs
7. Resolva o Funktor.hs
8. Resolva o Origami.hs
9. Demonstre que: not é uma involução: not . not = id
10. Complete as igualdades e demonstre:

    take n xs ++ drop n xs  =
    take m . drop n  =
    take m . take n  =
    drop m . drop n  =
    map g . map f  =
    sum . map double  =
    sum . map sum  =
    sum . sort  =
    map f . reverse  =
    concat . map concat  =
    filter p . map f  =
    

11. Quais das seguintes são válidas e quais não?

    map f . take n  =?=  take n . map f
    map f . reverse  =?=  reverse .map f
    map f . sort  =?=  sort . map f
    filter (p . g)  =?=  map ginv . filter p . map g
    reverse . concat  =?=  concat . reverse . map reverse
    filter p . concat  =?=  concat . map (filter p)
    

    (suponha aqui que a glinv é um inverso esquerdo da g, ou seja: glinv . g = id

2022-11-04

1. Demonstre (e investigue o que a contece com valores bottomosos, parciais, infinitos, etc.) as:

   length . reverse = length
   reverse . reverse = id
   associatividade da (++)
   map id = id                  [functor law 1]
   map (f . g) = map f . map g  [functor law 2]
   length (xs ++ ys) = length xs + length ys
   sum (xs ++ ys) = sum xs + sum ys
   product (xs ++ ys) = product xs * product 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
   

2022-11-12

1. Complete as igualdades e demonstre:

   cross (f,g) . pair (h,k)  =
   pair (f,g) . h  =
   fst . cross (f,g)  =
   snd . cross (f,g)  =
   cross (f,g) . cross (h,k)  =
   

2. Demonstre ou refute:

   map f . filter p  =?=  map fst . filter snd . map (pair (f,p))
   

3. Descubra as leis sobre o do:

   -----------------
   do x ← p         |
      return x      | = ???
   -----------------
   
   -----------------
   do x ← return  e |
      f x           | = ???
   -----------------
   
   -----------------
   do y ← do x ← p  |
             f x    | = ???
      g y           |
   -----------------
   

4. Resolva o ExIOwarmup.hs
5. Resolva o ExIO.hs Obs: Consulte o read.txt para aprender como usar a read

2022-11-16

1. Resolva o FA.hs
2. Estude as secções Semigroup, Monoid, Functor, Applicative do Typeclassopedia
3. Estude o capítulo 7 do [Hutton]
4. Estude o capítulo 6 do LYAH
5. Estude o capítulo 6 do [Bird]

2022-11-24

1. Estude a §10.1 do [Bird]
2. Estude o paper Hutton-fold
3. Estude o capítulo 9 do [Bird]
4. Estude o capítulo 10 do [Hutton]
5. Estude o capítulo 12 do [Hutton]
6. Estude o capítulo 14 do [Hutton]
7. Estude o capítulo 7 do [Bird]
8. Resolva o Foldinhos.hs

2022-11-29

1. implemente um Hangman aceitável, e outros jogos simples: ConnectFour, TicTacToe, Nim, etc.
2. Estude o paper Functional programming with bananas, lenses, envelopes, and barbed wire dos Meijer et al
3. Complete o FA.hs para instanciar os Monads também.
4. Brinque com os módulos da hierarquia FAM:

   import Data.Functor as F
   import Control.Applicative as A
   import Control.Monad as M
   

Histórico

2022-08-23: Aula 01: Intro [video]

• Burocracia da disciplina
• Linguagens de programação: overview
• Imerativas vs Declarativs
• Linguagens de programação
• Tipagem: static vs dynamic
• Tipos vs Dados
• Tipos dependentes
• Estratégia de evaluação
• casamento com padrão
• Lazy vs Strict
• λ-calculus

2022-08-25: Aula 02: primeiros passos [video]

• o REPL da Haskell: ghci
• tipos, type inference
• currificação
• domínio e codomínio de função
• o → dos típos é associativo à direita: a → b → c → d significa a → (b → (c → d))
• prefixa vs infixa; nomes com letras vs com símbolos
• backticks para usar função com nome normal em posição infixa
• a aplicação de função é associativa à esquerda: f x y z significa ((f x) y) z
• difernçá com as parenteses de LISP
• todas as funções são de aridade 1?
• oi

2022-08-29: Aula 03: [video]

• setting up
• nosso primeiro arquivo (module)
• módulo: uma colecção de declarações (definições)
• nosso primeiro erro e como ghci é um amigo
• sempre escreva os tipos
• inferindo tipo sem nenhum cálculo
• usando o it no ghci
• não confunda o = da haskell com assignment
• variáveis vs constantes; proibido redefinir algo
• x = valor no ghci vs em Haskell
• nossa primeira função
• variáveis
• escópos
• sombreamento (shadowing) e capturamento de variáveis
• erro de ética
• o modelo computacional da Haskell
• açúcar sintáctico e desugaring
• mais shadowing/capturamento de variáveis
• undefined; cálculos infinitos; lazy vs strict
• o tipo de undefined
• inconsistência lógica de Haskell
• um erro de tipagem: cuidado com as parenteses
• precedência e associatividade de operadores binários
• definições com mais que uma equação
• a ordem de equações numa definição importa
• usando o _
• Av.hs: média de dois números

2022-08-31: Aula 04: Types e kinds [video]

• Recap
• melhor considerar o = da Haskell como direcionado da esquerda pra direita
• estratégias de evaluação
• definindo usando equações e suas variáveis
• a ordem de equações numa definição importa
• usando o underscore
• a ordem das definições num módulo não importa
• Int vs Integer; typeclass Integral
• LiveCoding passado: o typeclass Fractional
• Uma resolução não currificada
• Pattern matching com tuplas
• Tipos; typeclasses; construtores de tipos; kinds
• dois [] diferentes
• mais: kinds vs types
• dois (,) diferentes
• criando nossos próprios tipos
• Weekday
• habitantes de tipos
• nextDay
• opção de ghci: +t
• Show
• deriving (Show)
• nextWorkingDay: três versões
• imitando Haskell para evaluar uma expressão
• inferando o tipo
• redex
• preguiça, mas…
• quanto dum valor Haskell vai calcular?
• quantas vezes vai efetuar o mesmo cálculo?
• aplicação de função, precedência, associatividade do apply default (espaço) vs ($)
• Boolean.hs

2022-09-05: Aula 05: primeiros passos [video]

• Prelude
• LiveCoding anterior: booleanos
• Mais sobre nossos booleanos
• if-then-else expressions
• igualdade: (==) e Eq
• typeclasses e instanciando tipos
• Os números naturais
• construtor de valores (data) vs função
• a typeclass Num
• estilo pointless (ou point-free)
• mais sobre infix vs prefix
• Haskell é preguiçosa mas não pode inferir do nada teoremas para ajudar sua preguiça
• Nats.hs

2022-09-06: Aula 06: algebraic data types [video]

• igualdade de funções: extensional vs intensional
• Pouco mais sobre λ-cálculo
• β e currificação
• η e definindo com parametros vs com lambdas
• α
• ADT (algebraic data types)
• data constructors de aridade zero ou mais
• type synonyms vs data types
• moradores de mundo Types vs de mundo Data
• Implementado os (Int,Int) (Int,Char) (Char,Char) etc.
• Parametrizando nossos tipos: type constructors de aridade maior que zero
• Implementando o tipo [Int]

2022-09-12: Aula 07: algebraic data types [video]

• ListInt
• destrutores vs construtores
• o famoso Cons e como representar uma lista
• tipos recursivos (também inductivos)
• parametrizando para chegar no List α
• voltando ao Nat
• calculando com recursão: 2+3=5
• Haskell vs matemática
• casando padrões
• construtor vs função
• quando não derivar a typeclass Eq?
• implementando a show para Nat
• o poder da recursão
• o açúcar sintáctico da Haskell para listas
• cons vs concatenação: (:) vs (++)
• length
• (x:xs) vs [x]++xs
• a convenção de usar nomes no plural pra listas
• o que nos permitiu definir funções por recursão?
• reverse
• where
• case .. of para pattern-matching
• pattern-matching mais complexo
• guards
• LiveCoding: Implementando o (++)

2022-09-14: Aula 08: Listas [video]

• import e import qualified
• como trabalhar nos módulos de Exercícos
• reverse sem o (++)
• pensando declarativamente
• podem usar expressões if-then-else e guards
• recursão nos inteiros da Haskell
• listas de Haskell
• sintaxe [from .. to]
• listas infinitas: [from ..] de boas
• take
• recursão em multiplos argumentos
• list comprehension
• filtros
• lambdas em Haskell
• secções em Haskell e expressões com buracos
• map

2022-09-19: Aula 09 [video]

• :browse
• Data.Char
• (re)descobrindo o map: scream e squareAll
• desabafando: A haskell!
• ord e chr
• pointless style (point-free)
• composição e suas propriedades
• associatividade de composição: de intuição para demonstração formal
• identidades
• Higher-order functions (funções de ordem superior)
• filter, takeWhile, dropWhile

2022-09-21: Aula 10: Listas [video]

• head e tail
• pattern matching com expressões case..of
• pattern matching mais profundo
• null
• length
• sum e product
• reverse e snoc
• flip
• dados e alvos definindo função
• teaser: procurando inhabitantes de tipos
• duas concatenações diferentes
• Ordering, compare
• contraints na definição de classes
• minimum e maximum
• faz sentido da vazia?
• a typeclass Bounded
• instanciando o mesmo tipo com outras implementações de classes
• alterando e discutindo sobre o minimum
• funções em Haskell são funções mesmo, e um teaser: thunks
• let..in expressions
• take e drop
• recursão em mais que uma parametro e seus presentes
• ExFromWhile
• fromWhile ; fromTo ; fromFor ; fromToThat

2022-09-28: Aula 11: Composição ; Encapsulamento ; Bottoms [video]

• usando composição
• livecoding: fromFor, fromTo, FromToThat
• reescrevendo mecanicamente para eliminar os pontos
• respostas no livecoding
• a ordem da compor
• encapsulamento: escondendo e expondo conteudo de módulos
• data constructors vs smart constructors
• instanciando o mesmo tipo numa typeclasse em duas maneiras diferentes
• Boxes e bottoms
• tipos isomórficos
• bottom

2022-09-28: Aula 12: Bottoms ; Maybe [video]

• Recap: Box e bottoms
• type constructor vs data constructor
• Bool vs Box Bool e seus bottoms
• undefined vs error vs bottom
• type-level programming teaser: tem bottom?
• Distingüindo entre bottoms e valores em geral
• SomeValues
• Box bottom vs bottom: casamento de padrões
• Quais são os habitantes do Nat?
• números parciais
• atLeastTwo e calculando
• two + atLeast two
• chegando ao infinito
• a (+) não é comutativa! Tem como melhorar?
• newtype vs data vs type
• Explicação
• funções parciais vs funções totais
• de head para Maybe
• um alvo impossível que vira possível para tipo concreto, como o Nat
• Maybe
• umas funções estranhas com Maybes

2022-10-06: Aula 13: Brigas ; caligrafia ; Maybe ; composição [video]

• Brigando
• bom uso de parenteses
• bom uso de linebreaks
• bom uso de indentação
• bom uso de whitespace
• bom uso de guards
• bom uso de pattern-matching
• nunca use TABs
• boa escolha de nomes de parametros
• elimina equações inúteis
• des-chuveirinho num «if-then-else»
• nunca: if b then True else False
• nunca: if b then False else True
• nunca: b == True
• nunca: b == False
• nunca desconstrua um valor apenas para re-construi-lo
• at-patterns
• o tipo duma expressão «case-of»
• nunca: length xs == 0
• habito lisposo: não fique usando head e tail; use pattern-matching
• at-patterns de novo
• «se tudo acaba explodindo o PC, qual seria o papel do Maybe?»
• safeHead
• firstThat: como usar composição
• um cálculo com listas infinitas
• «não teria chances de ver 11 sem ter chances também de explodir»
• por que deu certo?
• dá pra tirar todos os pontos?
• isGoodFirstThat
• seria legal… ter um maybeize
• language extensions de Haskell
• LambdaCase
• ExMaybe: tryToModifyWith

2022-10-07: Aula 14: Enum ; Sorting [video]

• firstThat
• lembrando o cálculo que deu certo: (safeHead . filter p) [0..]
• desugarizando os [x ..], [x .. z], etc.
• enumFrom(To)(Then)
• implementar os enumFrom… para os Nats
• Sorting
• como organizar o módulo
• assumptions
• merge
• at-patterns

2022-10-11: Aula 15: Sorting ; Testing ; Either [video]

• constraints nas instances
• sobre o uso de import qualified (as)
• de volta pro merge sort
• divide and conquer
• halve
• pattern-matching no where
• entender/declarar os ASSUMPTIONS
• insertion sort
• insert
• Bird-style comments
• usando com TeX (e amigos)
• Either α β
• usando o Either para tratar informação de erros
• zip , zipWith

2022-10-12: Aula 16: Pair vs Either ; Diagramas comutativos [video]

• expondo um tipo sem ou com construtores
• Recap: de Maybe para Either
• Pair vs Either
• forall
• const vs fst
• Voltando na briga Pair vs Either
• produto cartesiano, união, cardinalidades
• qual operação de conjuntos corresponde no Either?
• chegando na operação de união-disjunta
• diagrama de Pair
• diagramas comutativo
• definir a h
• uma tentativa errada
• (um)a definição correta
• o diagrama agora comuta?
• Voltando na briga: Pair vs Either
• o que «é» mesmo o produto αβ?
• outl, outr, fst, snd, projecções
• co-: invertendo as setas
• o coproduto
• defina a h no diagrama do coproduto

2022-10-16: Aula 17: Recursão ; arvores ; unit type ; side-effects [video]

• recursão em listas
• tails
• inits
• subsequences
• as hyperoperações
• sorted usando zipWith
• any, all, and, or
• caligrafia: tipo quebrado em linhas
• Trees
• flatten
• tmap
• pensando em tipos como se fossem conjuntos
• void: parece mesmo com o conjunto vazio?
• tipos de C vs tipos de Haskell
• side-effects
• o que serve um tipo com apenas um valor (próprio)?
• () :: ()
• Unit vs Empty
• flatten, tmap

2022-10-22: Aula 18: Curry–Howard ; Lógica [video]

• curry e uncurry
• habitantes de tipos
• cI, cK, cS, cB
• Curry–Howard
• lógica clássica vs lógica intuicionista
• lembrete: as principais funções recursivas

2022-10-22: Aula 19: Curry–Howard ; Arith ; Functors [video]

• recap: Curry–Howard
• recap: Either
• Holes
• Record syntax
• Recursão mutual
• Implementando expressões de arithmetica
• o símbolo : em nomes de operadores
• Extensões da linguagem Haskell
• UnicodeSyntax
• LambdaCase
• GADTs
• Functors (um teaser)

2022-10-27: Aula 20: Listas ; Fold ; Functors ; Leis [video]

• recap: Arith: val e step
• iterate ; tillRep
• folds
• chegando no foldr abstraindo varias definições recursivas
• foldr
• homework: foldr vs foldl
• foldr1 e foldl1
• scanl e scanr
• somando pela esquerda
• accumuladores
• Hoogλe
• Functors
• uns fmaps malandros para o List
• as leis de functors
• demonstrando propriedades
• words . unwords ≟ id
• unwords . words ≟ id
• reverse deixa em paz os as listas-singletons
• tillRep

2022-10-28: Aula 21: Demonstrações ; Indução [video]

• Θ: reverse [x] = [x]
• Θ: not . not = id
• Θ: associatividade da (+)
• indução mais cedo
• indução em tipos inductivos

2022-11-04: Demonstrações ; IO [video]

• Decepção
• class=‘livecoding’>cp (produto cartesiano), inserts, insertAt
• Θ: length (replicate n x) = n
• Θ: rev . rev = id
• Pureza
• IO em Haskell
• umas primitivas de IO: putChar, getChar, return

2022-11-05: linguagens unitipadas (tipos dinâmicos) ; funções ; IO [video]

• inserts e insertAt
• a mentira de «tipos dinâmicos»
• diagramas comutativos e funções de graça
• cross
• pair
• pointwise
• dupe ; λx.2x+1 ; λx.2x²
• Mais IO
• notação do
• putStr

2022-11-09: Functor ; IO [video]

• Functors
• Functor IO
• o return não é como o return que conhecem de outros cantos (sujos)
• os side-effects importam!
• IOkit
• o tipo de if-then-else
• use nomes bons!
• parseando com read
• parseando com reads
• getSafeInt
• (≫)
• void
• skip
• newline
• putStr
• lnize
• putStrLn
• putCharLn
• as leis do do

2022-11-11: Leis ; Functors ; IO ; GHC [video]

• Leis de aritmética com listas
• Functors
• tomando cuidado com as leis
• fmap’ando sobre esturturas profundas
• IOkit
• interact
• Hangman
• echo: hGetEcho e hSetEcho
• Hangman0
• elabora o dicionario da tua linguagem em vez de ficar preso nos primitivos!
• getSecretLine
• do: indentação correta e do com chaves
• echoless e pause
• Raimundo!
• Main e main
• compilando com ghc
• consertando a tentativa: map putChar
• iomap, mapIO, sequenceIO, sequenceIO_, …
• exemplo pra brincar: ConnectFour

2022-11-16: IO ; Semigroup ; Monoid [video]

• IOkit
• (≫)
• echoless
• pause ; void
• perdendo o do, podemos fazer tudo com o (≫)
• skip e newline: qual o sentido?
• putStr
• lnize ; putStrLn ; putCharLn
• interact ; perlineize
• when ; unless
• forever
• Kleisle composition
• bind, aka (≫=)
• umas ferramentas de Functor
• ap ; iomap
• filterIO
• sequenceIO e sequenceIO_
• NonEmpty
• Semigroup e Monoid

2022-11-17: Semigroup ; Monoid ; Functor ; Applicative [video]

• Semigroup–Monoid–Group
• Functor–Applicative–Monad
• Functor
• Applicative
• Applicative Maybe
• applicative style
• Applicative []: duas instanças diferentes

2022-11-23 (por Gustavo Gorgônio): Folds [video]

• foldr
• foldr1
• foldl
• foldl1
• foldl'
• exercícios
• badId
• sum
• any
• reverse
• minimum
• inits

2022-11-24 (por Gustavo Gorgônio): Folds ; Unfolds [video]

• inits
• banana split: (sum,lengh,odds)
• banana split: take
• eficiência: concat com foldl vs com foldr
• fold para outros tipos (não-listas)
• List α
• Nats
• Nats
• Either α β
• Tree α
• NonEmpty α
• unfold
• data vs codata ; constructors vs destructors ; recursão vs corecursão

2022-11-29: Strictness ; Functor-Applicative-Monad [video]

• thunks
• strictness
• a hierarquia F-A-M
• fmap em termos de Applicative
• Chegando em Monad
• return já tá no Applicative
• decepção: (≫)

2022-11-29: Functor-Applicative-Monad [video]

• a decepção returns
• Functor
• Applicative
• Monad
• Divarith
• Uma limitação de Applicative

2022-12-01: Monad ; Programação por cálculo e demonstração [video]

• recap: Divarith, applicative, join
• a decepção returns even stronger
• bind, kleisli composition, do
• join
• bind e do
• sobre as leis de monad
• Maybe é um monad
• resolvendo o Divarith, monadamente
• bibliotecas e mundo real
• programação por demonstração e cálculo

Futuro (fluido)