2019.2 Programação Funcional

Horários:24T12 [13h00–14h40]
Sala de aulas:A305
Sala do prof:A225
Contato:thanos@imd.ufrn.br
Horário de atendimento:mande email para marcar
Uso do servidor:tips
Turmas anteriores: 2018.1

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.

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) atrapalha 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

Bibliografia

Principal

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

Papers

Auxiliar

Links

Haskell ; Idris ; PureScript ; Neovim ; Emacs

Avaliação

Pontos

A disciplina não é dividida em 3 unidades (vejá Conteudo). Mesmo assim, cada aluno vai receber 3 notas, de 0 a 100 pontos. A nota U1 corresponde no LiveCoding; a U2 na prova escrita. A pior dessas duas notas sera a nota U3, exceto se o aluno optar para desenvolver um projeto, nesse caso a nota da U3 seria o max{nota-projeto,min{nota-livecoding,nota-prova}}.

Alem desses pontos, um aluno pode ganhar pontos extra: por participação; por homework; ou por provas-surpresas. Esses pontos valem igualmente com os pontos de provas escritas. Estou tenando ao máximo ser justo com esses pontos, mas nenhuma justificativa será dada por ganhar (ou não ganhar, ou perder!) pontos extra.

Umas regras: (1) nunca dê uma resposta que tu não pensou sozinho; (2) não tente “forçar a barra” dando respostas aleatórias nas minhas perguntas com objetivo único de ganhar pontos extra.

Umas provas escritas podem ter pontos bônus. Esses são pontos que são condicionalmente considerados: para considerá-los um aluno precisa ter pelo menos 50pts normais (não-bônus). As questões que valem pontos-bônus são em geral em assuntos auxiliares que, mesmo que merecem ser reconhecidos, não devem ser determinantes para aprovar na disciplina.

Presenças

Veja notícia no SIGAA para informações sobre presenças, chamadas, etc.

Live Coding

Durante cada aula, tem um momento onde eu boto um desafio para resolver (programar) na hora, no servidor, que envolve a criação dum certo arquivo (em geral o arquivo é um programa Haskell, que deve ser compilável pelo compilador do servidor).

O que serve esse arquivo?

  • a existência dele serve como "chamada";
  • a corretude do programa nele, serve como pontos para a unidade correspondente.

participantes ativos:
andreon arnaldoeloi arturprocopio danbarbosa doug dtayna er9 erickson eudnaolivio fortaleza555 gabriel giordanorn gustavo hdgamer21 joelfelipe338 junior karinepcdc leonandro m4theush marciotenorio marujo mauricio melosomelo nalbertg patricko ruivenzo songcosta versinho xmindgatex
sem conta:
(O resto dos alunos. Cadê?)

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: 108; bonus: 0) (dia: 27/11/2019)
    { uncensored }

Projeto

Mais informações logo.

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

Pontos de participação

T12
Gustavo 20
doug 12
Gabriel 10
er9 13
Arnaldo 8
Karine 10
Leonandro 4
Giordano 9
Maurício 12
Junior 24
Artur 8
dtayna 15
Andreon 5
gorgon 2

Homework

Os arquivos existem no servidor no ~/funfiles.

Olhem com freqüência para possíveis modificações/correções!

Pre...

  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.)

24/07/2019

  1. Estude a secção «Um toque de lambda» do capítulo «Funções» do [fmcbook].

15/08/2019

  1. Estude os capítulos 3 e 4 do [Hutton]
  2. Estude os capítulos 2–4 do [LYAH]
  3. Estude os «linguagens» e «Naturais, recursão, indução» do [fmcbook]
  4. Defina todos os undefined no ExBool.hs

19/08/2019

  1. Lembra o único homework do dia 24/07/2019 que tu não fez? Faça!
  2. Estude o capítulo «Funções» do [fmcbook] até a §136
  3. (Sem roubar) qual é o tipo de error?

20/08/2019

  1. Percebeu o RPG.hs?

21/08/2019

  1. Complete o ExNat.hs
  2. Complete o ExList.hs
  3. Complete o ExRat.hs
  4. Complete o ExMatrix2x2.hs
  5. Complete o ExComplex.hs
  6. Estude o capítulo 5 do [LYAH]

01/09/2019

  1. Complete o ExFromWhere.hs; defina cada função usando apenas uma curta equação.

04/09/2019

  1. Complete o ExBox.hs.
  2. Complete o ExBottom.hs.
  3. Termine o homework do dia 21/08/2019.

09/09/2019

  1. Complete o ExMaybe.hs.

10/09/2019

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

11/09/2019

  1. Resolva o ExFirstThat.hs, mas essa vez numa maneira legal.
  2. 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!

17/09/2019

  1. Resolva o ExSet.hs; estude as primeiras secções do capítulo «conjuntos» do [fmcbook]
  2. Defina elementariamente uma função halve ∷ [a] → ([a],[a]) para ser usada no merge sort.

18/09/2019

  1. Resolva o ExEither.hs.
  2. Resolva o ExDrunk.hs.
  3. Resolva o ExHyper.hs.

19/09/2019

  1. Defina o sorted com uma equação só, usando o zipWith.

23/09/2019

  1. Termina finalmente o ExList.hs
  2. Termina finalmente o ExMaybe.hs
  3. Termina finalmente o ExEither.hs
  4. Resolva o ExCommonWords.hs
  5. [fmcbook]: Estude o Capítulo «Funções».
  6. Defina a filter usando a concat.

25/09/2019

  1. Resolva (rebaixe!) o ExCommonWords.hs seguindo as dicas da aula.
  2. Resolva o Inhabitants.hs

26/09/2019

  1. Q: not . elem False =?= and
  2. Resolva o ExUsing.hs
  3. Resolva o ExCurry.hs
  4. Resolva o ExCH.hs

02/10/2019

  1. Resolva o ExArith.hs
  2. Resolva o ExVArith.hs
  3. Resolva o Funktor.hs

08/10/2019

  1. Resolva o Origami.hs
  2. Demonstre que: not é uma involução: not . not = id
  3. 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  =
    
  4. 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

10/10/2019

  1. Estude o capítulo «Naturais, indução, recursão» do [fmcbook]
  2. 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]
    
  3. Assista as 14 aulas correspondentes (aulas #9–#22 na playlist de FMC1, 2019.2 [use os "ToCs" nas descrições dos vídeos para navegar].
  4. A resolução do A1 é a seguinte: «Sejam a,b inteiros. O a divide o b se e somente se ak = b para algum inteiro k. Agora resolva o resto da Prova 1.1 de FMC1 do semestre 2019.2.

12/10/2019

  1. Demonstre (e investigue o que a contece com valores bottomosos, parciais, infinitos, etc.) as:
    length (xs ++ ys) = length xs + length ys
    sum (xs ++ ys) = sum xs + sum ys
    product (xs ++ ys) = product xs * product ys
    

14/10/2019

  1. Demonstre (e investigue o que a contece com valores bottomosos, parciais, infinitos, etc.) as:
    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
    

16/10/2019

  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

21/10/2019

  1. Pelamor do Alonzo, pare de vacilar e faça finalmente os homeworks dos dias 08/10–16/10!

23/10/2019

  1. DEPOIS de terminar o homework do dia 21/10/2019, implementa um Hangman aceitável, e outros jogos simples: ConnectFour, TicTacToe, Nim, etc.

05/11/2019

  1. Resolva o FA.hs
  2. Estude as secções Semigroup, Monoid, Functor, Applicative do Typeclassopedia

11/11/2019

  1. Estude o capítulo 7 do [Hutton]
  2. Estude o capítulo 6 do [LYAH]
  3. Estude o capítulo 6 do [Bird]
  4. Resolva o Foldinhos.hs
  5. Estude o paper [Hutton-fold]
  6. Estude o paper Functional programming with bananas, lenses, envelopes, and barbed wire dos Meijer et al

14/11/2019

  1. Resolva os homeworks de Functor e Applicative
  2. Resolva tudo que não tem feito ainda!

21/11/2019

  1. Brinque com os módulos da hierarquia FAM:
    import Data.Functor as F
    import Control.Applicative as A
    import Control.Monad as M
    
  2. Use a método que usamos para melhorar a reverse para melhorar o flatten dos binary trees que carregam informação apenas nas suas folhas:
    data Tree α = Leaf α
                | Node (Tree α) (Tree α)
    

23/11/2019

  1. Complete o FA.hs para instanciar os Monads também.

Histórico de aulas

24/07/2019: Intro [video]

  • Burocracia da disciplina
  • Linguagens de programação
  • Tipagem
  • Estratégia de evaluação
  • λ-calculus

29/07/2019: Mini-curso Unix [video]

31/07/2019: Mini-curso Unix [video]

02/08/2019: Mini-curso Unix [video]

05/08/2019: 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
  • teoria: type inference; currificação
  • types: Char; Ιnt
  • type constructors: – → –; [–]
  • type classes: Num
  • ghci: :type
  • funções: (+); (++); reverse; min; fst

07/08/2019 [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
  • 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
  • teoria: o modelo computacional da Haskell; lazy vs strict evaluation; versão baby de teorema Church-Rosser; açúcar sintáctico; inconsistência lógica
  • types: Integer
  • ghci: :edit :info it
  • haskell: modules; comentarios com --; a ordem de equações numa definição importa; undefined; precedência e associatividade de operadores binários; o _ casa com qualquer termo sem dar nome a ele

12/08/2019: 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
  • teoria: ontologia de haskell: types vs kinds ; type constructors ; habitantes de tipo ; redex
  • types: Bool
  • type constructors: [] (→) (,) (,,)
  • type classes: Fractional ; Integral ; Show
  • Haskell: data ; dois objetos diferentes chamados [] e dois chamados (,) etc. ; indentação ; deriving ; usando ' nos nomes ; ($)
  • ghci: :kind ; :set +t

14/08/2019: primeiros passos [video]

  • Recap
  • 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
  • theory: Nats; recursão; construtor de valores (data) vs função
  • types: Nat
  • typeclasses: Num, Eq
  • Haskell: Prelude, instance ; if-then-else

19/08/2019: 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]
  • theory: λ-calculus (α, β, η); currificação; data constructors vs type constructors
  • types: Pair α β
  • type constructors: Pair
  • Haskell: type (synonym) ; head ; tail ; error

21/08/2019: 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
  • Implementando o (++)
  • theory: tipos recursivos (ou inductivos) ; recursão ; pattern-matching in depth
  • types: Nat ; List α
  • Haskell: (:) ; açúcar sintáctico para listas ; where ; case-of ; if-then-else ; guards ; otherwise

26/08/2019: 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
  • theory: expressões com buracos, objetos infinitos, bottom
  • typeclasses: Enum

28/08/2019 [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
  • theory: composição de funções, associatividade, identidade, demonstração, estilo point-free, higher-order
  • Haskell: Data.List, Data.Char, map, filter, takeWhile, dropWhile
  • ghci: :browse

02/09/2019: 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
  • theory: procurando inhabitantes de tipos
  • types: Ordering
  • typeclasses: Ord ; Bounded
  • haskell: let..in ; compare ; flip

04/09/2019: 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
  • theory: composição ; bottom ; tipos isomórficos
  • types: Angle ; Box α
  • type constructors: Box
  • Haskell: encapsulamento ; bottom

09/09/2019: 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
  • theory: números parciais, número infinito
  • types: Maybe α
  • type constructors: Maybe
  • Haskell: Type(..)

11/09/2019: 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
  • Haskell: at-patterns ; indentação
  • extensions: LambdaCase

16/09/2019: 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
  • theory: sorting , merge sort
  • typeclasses: Enum
  • functions: enumFrom , enumFromTo , enumFromThen , enumFromThenTo

18/09/2019: 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
  • theory: insertion sort, quick sort, divide and conquer , literate programming
  • type constructors: Either
  • typeclasses: constraints
  • Haskell: literate programming (.lhs) , QuickCheck

23/09/2019: 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
  • theory: diagrama comutativo, união-disjunta, produto, coproduto
  • types: Pair α β vs Either α β
  • Haskell: Type(..) syntax

25/09/2019: 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
  • theory: side-effects, função pura, Unit type
  • types: Tree α, Tree α β, Unit, Empty
  • type constructors: Tree
  • Haskell: () :: ()

30/09/2019: 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
  • theory: Curry–Howard, currificação, habitação de tipos, lógica intuicionista
  • types: Bottom, Unit

02/10/2019: 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)
  • theory: recursão mutual
  • types: Arith
  • typeclasses: Functor
  • Haskell: Record syntax ; o símbolo :
  • ghc: holes (buracos)
  • extensions: UnicodeSyntax ; LambdaCase ; GADTs

07/10/2019: 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
  • theory: folds ; laws ; functor laws ; acumulador
  • typeclasses: Functor (laws)
  • Haskell: Hoogle
  • funções: iterate , foldr , foldl , foldr1 , foldl1 , scanl , scanr

09/10/2019: Demonstrações ; Indução [video]

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

14/10/2019: Demonstrações ; IO [video]

  • Decepção
  • cp (produto cartesiano), inserts, insertAt
  • Θ: length (replicate n x) = n
  • Θ: rev . rev = id
  • Pureza
  • IO em Haskell
  • umas primitivas de IO: putChar, getChar, return
  • theory: indução ; IO ; pureza
  • Haskell: IO
  • type constructors: IO
  • types: IO () ; IO Char
  • functions: putChar ; getChar ; return
  • GHCi: como comporta: mais detalhes sobre seus passos

16/10/2019 unitipada (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
  • theory: a verdade sobre linguagens com tipos «dinámicos» (unityped) ; estilo pointless (point-free) ; diagramas comutativos
  • Haskell: notação do
  • types: IO () ; IO Char
  • functions: cross ; pair ; dupe ; putStr

21/10/2019: 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
  • LiveCoding
  • (≫)
  • void
  • skip
  • newline
  • putStr
  • lnize
  • putStrLn
  • putCharLn
  • as leis do do
  • theory: leis de functor ; leis de do
  • Haskell: notação do ; let-binding
  • functions: read ; reads

23/10/2019: 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
  • theory: leis de aritmética descritas com listas ; leis de functor
  • Haskell: Main e main
  • functions: main ; hGetEcho ; hSetEcho
  • GHC: compilação

30/10/2019: 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 (≫=)
  • umas ferramentas de Functor
  • ap ; iomap
  • filterIO
  • sequenceIO e sequenceIO_
  • NonEmpty
  • Semigroup e Monoid
  • theory: Semigroup ; Monoid
  • functions: (≫) ; bind (≫=) ; interact ; when ; sequence

04/11/2019: Semigroup ; Monoid ; Functor ; Applicative [video]

  • Semigroup–Monoid–Group
  • Functor–Applicative–Monad
  • Functor
  • Applicative
  • Applicative Maybe
  • applicative style
  • Applicative []: duas instanças diferentes
  • theory: Semigroup ; Monoid ; Group ; Functor ; Applicative
  • functions: (⋄) ; sconcat ; stimes ; mconcat ; mempty ; pure ; splat (◈)

06/11/2019 (por Gustavo Gorgônio): Folds [video]

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

11/11/2019 (feat. 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
  • Aqui.hs
  • theory: codata, corecursão
  • functions: unfold

13/11/2019: [video]

  • thunks
  • strictness
  • a hierarquia F-A-M
  • fmap em termos de Applicative
  • Chegando em Monad
  • return já tá no Applicative
  • decepção: (≫)
  • theory: lazy evaluation , thunks , strict functions
  • functions: seq , ($!) , return , (≫)
  • Haskell: strictness bang (!)
  • ghci: :print ; :sprint

18/11/2019: [video]

  • a decepção returns [00:00:00]
  • Functor [00:01:45]
  • Applicative [00:24:18]
  • Monad [00:44:35]
  • Divarith
  • Uma limitação de Applicative
  • Castigo2.hs
  • functions: ‹$ ; $› ; ‹$› ; ‹* ; *› ; ‹*› ; ‹*› ; void

20/11/2019: [video]

  • recap: Divarith, applicative, join [00:00:00]
  • a decepção returns even stronger [00:08:11]
  • bind, kleisli composition, do [00:09:41]
  • join [00:11:22]
  • bind e do [00:28:29]
  • sobre as leis de monad [00:43:07]
  • Maybe é um monad [00:48:37]
  • resolvendo o Divarith, monadamente [00:57:52]
  • bibliotecas e mundo real [01:05:24]
  • programação por demonstração e cálculo [01:10:36]
  • theory: monad ; programação por demonstração e cálculo
  • functions: join ; (»=)
  • Haskell: notação do ; ApplicativeDo

27/11/2019: Prova escrita

04/12/2019: Assuntos auxiliares

  • posets, CPOs, limites
  • λ-cálculo: Church numerals, booleans, etc.
  • Dependent types

06/12/2019: Apresentações de projetos

Futuro (fluido)

Last update: Fri Dec 6 21:04:12 -03 2019