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

Horários de aula: EaD, assíncrono
Horários de avaliações síncronas: 7M3456 [08h55–12h30]
Contato:thanos@imd.ufrn.br
Playlists: FMC1 2019.2 (aulas gravadas)
Monitoria/TA: fmc.imd.ufrn.br (Começou!)
Turmas anteriores: ..

Info

Pré-requisitos

Nenhum, além dos óbvios:

  • {vontade, tempo} para {hackear, praticar, procurar, implementar, programar} nos assuntos da disciplina;

Obs.: 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. Programação é uma delas.

Experiência com programação não-funcional (disfuncional) atrapalha mas NÃO será estritamente proibida. ;)

(Obs.: estudarler.)

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 e referências

Conhece o libgen?

Principal

Papers

Auxiliar

Por que tantos livros? Qual é o melhor? Vale a pena ler esse excerto do livro Linear Algebra de Jänich.

Links

Tecnologias & ferramentas

Obs.: As tecnologías/ferramentas seguintes podem mudar durante a disciplina—exceto a primeira. (Instalem e/ou criem uma conta para usar onde necessário.)

  1. Zulip (leia o FAQ).
  2. A linguagem de programação funcional Haskell (leia o FAQ).
  3. PAPEL (um caderno para dedicar à disciplina) e LAPIS/CANETA.
  4. Git (leia o FAQ).
  5. Muito recomendado mas não necessário: um sistema Unix (veja o minicurso Unix 2019.2).
  6. Muito recomendado mas não necessário: (neo)vim e Emacs.

Regras

  1. Nunca escreva algo que você mesmo não sabe explicar: (i) o que significa; (ii) seu papel na tua resolução. Por exemplo: um aluno escreveu a frase seguinte na sua demonstração: «Como f é cancelável pela esquerda temos que g=h». Ele deve saber o que significa ser cancelável pela esquerda e também explicar como isso foi usado e/ou o que isso tem a ver com essa parte da sua demonstração.
  2. Qualquer trabalho poderá ser questionado em forma de prova oral, em modo privado ou aberto. Se um aluno não consegue explicar o que ele mesmo escreveu numa resolução, será considerado plágio (veja abaixo).
  3. Participando, nunca dê uma resposta que tu não pensou sozinho, exceto dando os créditos correspodentes.
  4. Não tente “forçar a barra” perguntando ou respondendo coisas aleatórias com objetivo único de ganhar pontos. Os pontos de participação não correspondem em apenas perguntas ou dúvidas que mostram interesse. O interesse é implícito pelo fato que tu escolheu matricular nesta turma—não vale pontos.
  5. Não procurem resoluções em qualquer lugar fora dos indicados em cada homework. O único recurso aceitável para procurar ajuda é no nosso Zulip (especificamente seus canáis públicos—não DM) e a monitoria.

Uns deveres dos alunos

  1. Visitar o site e o Zulip da disciplina pelo menos uma vez por dia durante o semestre. (Qualquer coisa postada no site ou no Zulip da disciplina será considerada como conhecida por todos os alunos da turma.)
  2. Participar no Zulip diariamente.
  3. Estudar o conteúdo lecionado e tentar resolver todos os trabalhos atribuidos.
  4. Checar e atender seu email cadastrado no SIGAA pelo menos uma vez por dia durante o semestre.

(Veja também os FAQs relevantes.)

Sobre plágio

  1. Plágio detectado implica que o aluno será reprovado imediatamente por nota e por faltas.
  2. Entregar tuas resoluções para um aluno copiar é proibido do mesmo jeito, e também não ajuda mesmo ninguém.

Avaliação e faltas

Disclaimer. Eu suponho que os alunos desta turma escolheram se matricular por interesse em aprender seu conteudo. O ideal seria ignorar assuntos irrelevantes de avaliação, presenças, carga horária, etc., e se jogar nos estudos.

Avaliação

A nota final de cada aluno vai ser principalmente baseada em um ou mais dos: (i) provas escritas; (ii) sua participação; (iii) trabalhos atribuidos; (iv) projeto (opcional, veja o FAQ).

FAQs

Dynamic content

Pontos de participação

Provas

Consideração de projeto (como trabalho avaliativo) acontecerá apenas depois da correção das duas primeiras provas.

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

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
  • 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

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
  • 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

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

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

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 (++)
  • 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

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

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
  • 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

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

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
  • theory: composição ; bottom ; tipos isomórficos
  • types: Angle ; Box α
  • type constructors: Box
  • Haskell: encapsulamento ; 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
  • theory: números parciais, número infinito
  • types: Maybe α
  • type constructors: Maybe
  • Haskell: Type(..)

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

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

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

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

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

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

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

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

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
  • theory: indução

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
  • 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

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
  • 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

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
  • theory: leis de functor ; leis de do
  • Haskell: notação do ; let-binding
  • functions: read ; reads

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

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
  • theory: Semigroup ; Monoid
  • functions: (≫) ; bind , (≫=) ; interact ; when ; sequence

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
  • theory: Semigroup ; Monoid ; Group ; Functor ; Applicative
  • functions: (⋄) ; sconcat ; stimes ; mconcat ; mempty ; pure ; splat , (◈)

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

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

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
  • theory: codata, corecursão
  • functions: unfold

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: (≫)
  • theory: lazy evaluation , thunks , strict functions
  • functions: seq , ($!) , return , (≫)
  • Haskell: strictness bang (!)
  • ghci: :print ; :sprint

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

  • a decepção returns
  • Functor
  • Applicative
  • Monad
  • Divarith
  • Uma limitação de Applicative
  • functions: ‹$ ; $› ; ‹$› ; ‹* ; *› ; ‹*› ; ‹*› ; void

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
  • theory: monad ; programação por demonstração e cálculo
  • functions: join ; (»=)
  • Haskell: notação do ; ApplicativeDo

Futuro (fluido)

Sem futuro! Acabou!

Last update: Sat Dec 17 17:33:24 -03 2022