Ricorsività e specialità

Dell’ottimo Michael Burge 💥 non so molto; lo si trova su Twitter, ha un blog pieno di cose troppo nerdose per me. È nuovo, giovane immagino e per me un maestro. Ecco un suo tweet, muto, cioè subito via con il codice.

Ma funzionerà? mi sembra troppo semplice, forse è meta…

Non resta che provare

* rec $ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude> fibs !! 8
21
Prelude> fibs !! 12
144
Prelude> fibs !! 0
0

La prima riga definisce la funzione fibs che crea la lista infinita dei numeri di Fibonacci fornendo i valori dei primi 2 e definendo il valore del successivo come (+) dei valori della lista stessa. !! estrae l’elemento indicato nella lista. Semplice vero? l’ho capita anch’io. E siccome Haskell è lazy –OK, non voglio ripetermi.

OK, ma io preferisco Racket allora ecco. È comodo eseguirlo nel suo ambiente di sviluppo, DrRacket, perché devo caricare il linguaggio lazy:

Ma io sono della vecchia scuola, quella della REPL e allora ecco…

* rec $ racket
Welcome to Racket v6.11.
> (require lazy)
> (define fibs (cons 0 (cons 1 (map + fibs (rest fibs)))))
> (displayln (list-ref fibs 8))
21
> ^D
* rec $

OK. È la tradudione letterale del programma Haskell. Più verboso. Ma Michael (lo sapete che si è fatto un linguaggio tutto suo, Pyramid) non si ferma qui, va oltre. Per procedere devo acquisire il modulo sweet-exp e qui è comodo davvero DrRacket operando da menu: File/Install Package...

Fatto e allora (questa volta la REPL non basta):

Nota: il tweet contiene un errore, manca la parentesi aperta prima di +.

Nota per me: devo informarmi su Sweet, non sono l’unico anche Jesse 💥

Come se non bastasse ecco William 💥

Sì, avendo tempo ci sarebbe da vedere anche Cur.

⭕

Haskell 204 – OK ma…

L’ho tirata lunga con Haskell, in modo tutt’altro che razionale, colpa anche mia ma non solo. la pagina della documentazione del sito ufficiale comincia con libri per impaprare Haskell poi continua con Corsi, Tutorials e Risorse Online prima di arrivare a Manuali e Guide. Ecco, io ho seguito queste indicazioni con risultati non sempre soddisfacenti (a essere buono). Non sempre e non è colpa degli autori. Piuttosto Haskell, benché non sia un linguaggio nuovo, è tuttora in evoluzione, me ne sono accorto da tempo ma oggi aprendo la guida di GHC, qui, ne ho avuto una conferma terrificante.

La versione che ho installato

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.0.2

è vecchia, il manuale si riferisce alla 8.4.1, da intendersi come 8.4.

Nella versione corrente ci sono parecchie novità (per me). Considerando che i tutorial che ho seguito non erano recenti mi spiego le difficoltà trovate nel codice che tentavo di riprodurre.

Dovrei ripartire aggiornando la versione, cioè installando l’ultima, quella cui si riferisce la guida e ripartire. Ma non me la sento anche perché me lo sento che poi cambia ancora.

Dall’esame del tutorial del prof. Brent Yorgey ho visto che riesco a comprendere il codice, anche se avrei a volte difficoltà a scriverne di mio, forse a causa della mia storia pregressa, non funzionale. Sono però convinto che centri anche la filosofia del linguaggio, io sono più lato Python, ma anche Lisp, cioè Scheme, cioè Racket –rockz 💥

C’è un linguaggio, gia visto brevemente in passato che mi attira, Rust. Ma anche lui, vedo su Twitter, che le versioni si rincorrono velocemente. Chissà… 😁

In questi giorni da me la connessione a Internet funziona in modo molto saltuario; sono in una zona marginale e la manutenzione è tutt’altro che ottimale, secondo le ultime notizie l’ispezione tecnica è prevista per il 4 giugno, probabilmente salvo ulteriori rinvii. Ne sto approfittando offline con Python, rockz 💥

⭕

Haskell – 203 – basta posts con questo tutorial

Continuo da qui, copio qui.

In this module, we will explore some rudiments of parsing. Naturalmente c’è il file literate.

Ci sono esercizi da fare, siccome sono über-lazy sbircio le soluzioni e sì, si potrei (dovrei) farli.

Però –ci sto pensando da giorni ormai e ho deciso– quest posts sul corso del prof Brent Yorgey (ottimo) me li devo vedere in privato, non sono raccontabili. Poi, se userò Haskell (e non è detto) ci ricorrerò quando mi verrò a trovare in ambasce. Il modulo 18 —Monads— mi ha chiarito cose, in fondo non era come sembrava 😁

⭕

Haskell – 202 – il linguaggio Arith: pretty printing

Continuo da qui, copio qui.

OK, ottimo prof. Yorgey 💥 Ma siccome sono solo, non in classe faccio a modo mio. Oltre al file literate carico le soluzioni trovate qui.

Lo so che non sarebbe corretto in classe, ma sono atipico (e discolo 👽).

L’esame del codice mi permette (credo sia la prima volta) di vedere un caso pratico (a dire il vero manca ancora qualcosa per renderlo eseguibile fuori da GHCi ma fa parte del gioco).

La mia impressione (solo mia, non esportabile) è che il codice risulta molto normale, ritiro le accuse di matematicità distribuite in passato.

E continuo con l’esame, post corto, lo so 😎

⭕

Haskell – 201 – sintassi e semantica

Continuo da qui, copio qui.

Si parte caricando il file literate.

Poi cominciano le difficoltà: la lezione è OK se sei presente fisicamente, con i compagni più smart e il prof. Io sono qui solo, vecchio e quindi meno aggiornato e condizionato da cattive abitudini (ultimamente bash oltre a Python) e alle volte (anzi molto spesso) non riesco a stare al passo con la classe.

Ma ce la metto tutta, per esempio:

Prelude> :l 04-syntax-semantics.lhs
[1 of 1] Compiling Main             ( 04-syntax-semantics.lhs, interpreted )
Ok, modules loaded: Main.
*Main> parseMirror "L.R"
(Layer Middle,"")
*Main> parseMirror "L.L"
*** Exception: 04-syntax-semantics.lhs:(155,5)-(156,42): Non-exhaustive patterns in case

*Main> parseMirror "LL.RR"
(Layer (Layer Middle),"")
*Main> parseMirror "LL.RR.LL"
(Layer (Layer Middle),".LL")

Poi arriva l’esercizio vero, BIN:

--bin.hs

{-# LANGUAGE GADTs #-}

import Data.Char

-- http://ozark.hendrix.edu/~yorgey/360/f16/modules/04-syntax-semantics.html

data Bin where
    Hash :: Bin
    Layer :: Bin -> Bin -> Bin
    deriving Show

prettyBin :: Bin -> String
prettyBin Hash = "#"
prettyBin (Layer x y) = "(" ++ prettyBin x ++ prettyBin y ++ ")"


parseBin :: String -> Maybe (Bin, String)
parseBin ('#' : rest) = Just (Hash, rest)
parseBin ('(' : rest) =
    case parseBin rest of
        Just (x, rest') -> case parseBin rest' of
            Just (y, ')' : rest'') -> Just (Layer x y, rest'')
            _ -> Nothing
        _ -> Nothing
parseBin _ = Nothing

interpBin :: Bin -> Integer
interpBin Hash = 1
interpBin (Layer l r) = interpBin l + 2 * (interpBin r)

evalBin :: String -> Maybe Integer
evalBin xs = do
    (bin, _) <- parseBin xs
    return $ interpBin bin

{-
   ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
 ::= '#'
        | 
        | '('   ')'
-}

data EBin where
    EHash :: EBin
    Digit :: Int -> EBin
    ELayer :: EBin -> EBin -> EBin
    deriving Show

prettyEBin :: EBin -> String
prettyEBin EHash = "#"
prettyEBin (Digit d) = show d
prettyEBin (ELayer x y) = "(" ++ prettyEBin x ++ prettyEBin y ++ ")"

parseEBin :: String -> Maybe (EBin, String)
parseEBin ('#' : rest) = Just (EHash, rest)
parseEBin ('(' : rest) =
    case parseEBin rest of
        Just (x, rest') -> case parseEBin rest' of
            Just (y, ')' : rest'') -> Just (ELayer x y, rest'')
            _ -> Nothing
        _ -> Nothing
parseEBin (c : rest) | isDigit c = Just (Digit $ read [c], rest)
                     | otherwise = Nothing
parseEBin _ = Nothing

desugar :: EBin -> Bin
desugar EHash = Hash
desugar (Digit d) = grow d where
    grow 0 = Hash
    grow n = let inner = grow (n-1) in Layer inner inner
desugar (ELayer l r) = Layer (desugar l) (desugar r)


evalEBin :: String -> Maybe Integer
evalEBin xs = do
    (ebin, _) <- parseEBin xs
    return $ interpBin $ desugar ebin

*Main> :l bin
[1 of 1] Compiling Main             ( bin.hs, interpreted )
Ok, modules loaded: Main.
*Main> evalEBin "(#2)"
Just 19
*Main> evalEBin "(#4) (#2)"
Just 163
*Main> evalEBin "((#4) (#2))"
Nothing
*Main> evalEBin "((#4)(#2))"
Just 201
*Main> evalEBin "0"
Just 1
*Main> evalEBin "1"
Just 3
*Main> evalEBin "2"
Just 9
*Main> evalEBin "#"
Just 1
*Main> evalEBin "##"
Just 1
*Main> evalEBin "(##)"
Just 3
*Main> evalEBin "((##) (##))"
Nothing
*Main> evalEBin "((##)(##))"
Just 9

Uhmmmmysteryousassay 😯

Hai copiato? Sì, qui.

Devo rivedere profondamente il modo con cui affronto il corso.

⭕

Haskell – 200 – polimorfismo e liste – 3

Continuo da qui, copio qui, scrollare fino a “Strings“.

listLength []     = (0 :: Integer)
listLength (_:xs) = 1 + listLength xs

startsWith :: String -> String -> Bool
startsWith []     _      = undefined
startsWith (_:_)  []     = undefined
startsWith (x:xs) (y:ys) = undefined

What is the type of listLength? (Feel free to ask GHCi.)

Prelude> :l 03-polymorphism-lists.lhs
[1 of 1] Compiling Main             ( 03-polymorphism-lists.lhs, interpreted )
Ok, modules loaded: Main.
*Main> :t listLength
listLength :: [t] -> Integer

Evaluate startsWith "cat" "catastrophe". What happens?

*Main> startsWith "cat" "catastrophe"
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at 03-polymorphism-lists.lhs:157:30 in main:Main

OK, prof mi hai fregato! 😯 Bisogna sempre fare attenzione con gli smarts e Dr. Brent lo è assay.

Complete the definition of startsWith by replacing undefined with appropriate expressions. startsWith should test whether the second argument has the first argument as a prefix. For example:

startsWith "cat" "catastrophe" -> True
startsWith "ban" "banana"      -> True
startsWith ""    "dog"         -> True
startsWith "at"  "catastrophe" -> False
startsWith "dog" ""            -> False

Ci ho provato senza riuscirci; poi ho googlato e ho trovato una definizione che funziona ma usa cose non ancora viste. Usa cose non ancora viste quindi non è quella che vuole il prof. E non è mia, questa:

--startsWith.hs

startsWith :: Eq a => [a] -> [a] -> Bool
startsWith [] _ = True
startsWith _ [] = False
startsWith a b = and $ zipWith (==) a b

*Main> :l startsWith.hs
[1 of 1] Compiling Main             ( startsWith.hs, interpreted )
Ok, modules loaded: Main.
*Main> startsWith "cat" "catastrophe"
True
*Main> startsWith "ban" "banana"
True
*Main> startsWith "" "dog"
True
*Main> startsWith "at" "catastrophe"
False
*Main> startsWith "dog" ""
False

Questo mi mette in depressione; ho provato e riprovato con l’idea di farla ricorsiva: controllare che x e y siano uguali e && startsWith xs ys ma non ci sono riuscito. Il guaio di essere da solo, nessuno a cui poter chiedere. Poi mi trovo anche a pensare sempre da pythonista 😐

⭕

Haskell – 199 – polimorfismo e liste – 2

Continuo da qui, copio qui, scrollare fino a “Lists“.

Liste
Sempre con il file literate del post precedente, il concetto di lista.

Prelude> :l 03-polymorphism-lists.lhs
[1 of 1] Compiling Main             ( 03-polymorphism-lists.lhs, interpreted )
Ok, modules loaded: Main.
*Main> :t ints
ints :: [Integer]
*Main> ints
[3,5,92]

Evaluate length ints and length noInts.

*Main> ints
[3,5,92]
*Main> length ints
3
*Main> noInts
[]
*Main> length noInts
0

Explain what [] means. È la lista vuota, con zero elementi.

Evaluate moreInts and length moreInts.

*Main> moreInts
[7,3,5,92]
*Main> length moreInts
4

Probabilmente il prof vuole farmi notare come inserire items in una lista:

moreInts :: [Integer]
moreInts = 7 : ints

Do the same for yetMoreInts.

*Main> yetMoreInts
[4,2,3,5,92]
*Main> length yetMoreInts
5

Now evaluate ints. Has it changed?

No, ovviamente, verifica:

*Main> ints
[3,5,92]

Write an expression e such that length e evaluates to 6.

e :: [Integers] --questo non posso scriverlo in GHCi
*Main> e = [1..6]
*Main> e
[1,2,3,4,5,6]
*Main> length e
6

OK, .. me lo ricordavo e serve solo per risparmiare tastate.

Explain what the (:) operator does. Già detto, non sono ripetitivo, posso aggiungere che si chiama cons, come nel Lisp 😎

What will someInts evaluate to? How about length someInts? Write down your guesses before typing them into GHCi.
Facile: [8,42] ottenuto aggiungendo 8 e 42 a []; è un modo comune per construire liste.

Evaluate ints2. What do you notice?
Uh! appena detto 😎

When you reach this point, STOP and let Dr. Yorgey know. OK, Brent rockz 💥

⭕

Haskell – 198 – polimorfismo e liste – 1

Continuo da qui, copio qui.

Al solito c’è il file literate, pronto per seguire il prof Yorgey 😁, dovrei avere più tempo o ridurrò la frequenza di posting.

In this module we will complete our initial exploration of the Haskell programming language.

Maybe

data Maybe a where
  Nothing :: Maybe a
  Just    :: a -> Maybe a

Note that the above definition of Maybe does not have bird tracks in front of it since it is already defined in the standard library; I just wanted to show you its definition.

Uh! espressione nuova: bird track, googlato e trovato che è un modo di dire da haskellers, è questo >. Bastava fare attenzione, leggere il file literate. O essere presente a lezione, chiedere a quelli del gruppo (non al prof che poi magari si ricorda di te all’esame come quello che faceva le domande niubbe).

OK, non ricopio, provo invece se ho capito (non sono cose nuove, tante già viste, anche più volte).

Give two example values of type Maybe Bool.

--maybe-bool.hs

b :: Maybe Bool
b = Just (1 == 1)

*Main> :l maybe-bool.hs
[1 of 1] Compiling Main             ( maybe-bool.hs, interpreted )
Ok, modules loaded: Main.
*Main> b
Just True

How many distinct values of type Maybe (Maybe Bool) are there? List all of them.

-- mm-bool.hs

mmb :: Maybe (Maybe Bool)
mmb = Just (Just (1 == 1))

mmmb :: Maybe (Maybe (Maybe Bool))
mmmb = Just (Just (Just (1 == 1)))

Prelude> :l mm-bool.hs
[1 of 1] Compiling Main             ( mm-bool.hs, interpreted )
Ok, modules loaded: Main.
*Main> mmb
Just (Just True)
*Main> mmmb
Just (Just (Just True))

Ce ne sono tanti anche se devo capire cosa possano servire

How is safeDiv different from div?

--safeDiv.hs

safeDiv :: Integer -> Integer -> Maybe Integer
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)

showDiv :: Integer -> Integer -> String
showDiv x y = case safeDiv x y of
  Nothing -> "Division by zero"
  Just z  -> "Result is " ++ show z

*Main> :l safeDiv.hs
[1 of 1] Compiling Main             ( safeDiv.hs, interpreted )
Ok, modules loaded: Main.
*Main> safeDiv 12 5
Just 2
*Main> safeDiv 12 0
Nothing
*Main> div 12 5
2
*Main> div 12 0
*** Exception: divide by zero

Try showDiv on some examples.

*Main> showDiv 12 5
"Result is 2"
*Main> showDiv 12 0
"Division by zero"

What does the a in the definition of Maybe represent?
Il possibile valore su cui operare.

Write a function plusMaybe :: Maybe Integer -> Maybe Integer -> Maybe Integer which performs addition if both arguments are Just, and returns Nothing otherwise.

-- plusMaybe

{-# LANGUAGE GADTs #-}

plusMaybe :: Maybe Integer -> Maybe Integer -> Maybe Integer
plusMaybe (Just a) (Just b) = Just (a + b)

*Main> :l plusMaybe.hs
[1 of 1] Compiling Main             ( plusMaybe.hs, interpreted )
Ok, modules loaded: Main.
*Main> plusMaybe (Just 12) (Just 4)
Just 16

Fatto solo in parte, poi mi sono perso; vado a cercare ontehtoobz 😐

⭕

Haskell – 197 – dati di tipo algebrico e pattern matching

Continuo da qui, copio qui.

Nota solo per me: le raccomandazioni iniziali del prof 😁, davvero un peccato non essere ‘mericano 20yo.

Al solito c’è tutto il testo della lezione e il codice nel file literate.

Una cosa che avevo già intravisto ma non ancora non avevo affrontato:

{-# LANGUAGE GADTs #-}

The above {-# LANGUAGE #-} thingy turns on a Haskell language extension called “GADTs”, which stands for “Generalized Algebraic Data Types”. You need not worry about what that means for now; it will enable us to use some nice syntax. OK, resterà ancora da approfondire ma OK.

Prelude> :l 02-ADTs
[1 of 1] Compiling Main             ( 02-ADTs.lhs, interpreted )
Ok, modules loaded: Main.
*Main> :t Red
Red :: Color
*Main> :t colorChar
colorChar :: Color -> Char
*Main> :t isRed
isRed :: Color -> Bool

The data Color where ... declaration defines an algebraic data type (ADT) called Color. Red, Green, and Blue are called data constructors, or just constructors for short.

Try removing or commenting out the last line of the definition of colorChar. Reload the module and try evaluating colorChar Blue. What happens?

Lo so prof ma lo faccio; commento la riga, così: --colorChar Blue = 'b', salvo il file come 02-ADTs-m.lhs ed ecco:

*Main> :l 02-ADTs-m
[1 of 1] Compiling Main             ( 02-ADTs-m.lhs, interpreted )
Ok, modules loaded: Main.
*Main> colorChar Blue
*** Exception: 02-ADTs-m.lhs:(34,3)-(35,23): Non-exhaustive patterns in function colorChar

OK, il messaggio è esplicativo, c’è tutto quanto serve a correggere.

Now add {-# OPTIONS_GHC -Wall #-} as the very first line of this file (with a blank line after it), and reload again.

*Main> :l 02-ADTs-W
[1 of 1] Compiling Main             ( 02-ADTs-W.lhs, interpreted )
Ok, modules loaded: Main.
*Main> :t Red
Red :: Color
*Main> isRed Blue
False
*Main> isRed Yellow

:17:7: error:
    Data constructor not in scope: Yellow :: Color

in caso di errore cambia il messaggio; ecco perché bisognerebbe essere a lezione 😐

Altro su ADTs
Si possono fare cose come

*Main> mi1
No
*Main> mi2
Yes 6
*Main> Yes 10
Yes 10
*Main> unMaybe (Yes 6)
249

e

*Main> record1
NameAndAge "McGrew" 6
*Main> foo record1
20
*Main> record2
AddressAndEmail "55 Ridge Avenue" "mcgrew@mcgrew.com"
*Main> foo record2
23
*Main> record3
TopSecret 17 False ('x',10)
*Main> foo record3
23

Ho ancora problemi con la funzione proposta, rimandata a quando sarò più istruito, o avrò più tempo. Un problema mio è che Python mi condiziona, non mi consente di vedere soluzioni anche elementari, p.es. ... [] = 0. 😐

⭕

Haskell – 196 – introduzione a Haskell

Continuo da qui, copio qui.

Cose che voi umani… 😁 Per ogni lezione c’è il file di tipo “literate Haskell document” con, ahemmm, tutto, questo.

E, al solito, si usa GHCi, provo, dopo aver scaricato il modulo:

Prelude> :l 01-Haskell
[1 of 1] Compiling Main             ( 01-Haskell.lhs, interpreted )
Ok, modules loaded: Main.
*Main> i
-35
*Main> c
'Z'
*Main> s
"Hello, world!"
*Main> hailstone 15
46
*Main> hailstone 8
4

hailstone è la base della solita congettura di Collatz, quella del 3n+1. O meglio lo sarebbe se fosse resa ricorsiva, forse nelle prossime lezioni 😁

Dr. Brent Yorgey –posso d’ora in poi chiamarlo Brent, vero?– riesce a esporre i concetti elementari di Haskell arrivando fino alle guards. M’immagino la lezione, un paio d’ore frizzanti, fortunati gli studenti di CSCI 360 😁 Intanto resto in attesa di cosa verrà 😁

⭕