\begin{code}
{-# OPTIONS_GHC -Wall #-}
module Feb01 where
import Prelude hiding (Maybe(Nothing, Just), maybe, Either(..), either)
\end{code}
Learning objectives:
\begin{itemize}
\item polymorphic data types
\item modelling errors
\item edit distance: more on DSLs, interpreters, etc
\end{itemize}
binary tree with ‘arbitrary’ data at the nodes only.
\begin{code}
data Tree a = Nil | Node a (Tree a) (Tree a)
deriving Show
collapse :: Tree a -> [ a ]
collapse Nil = []
collapse (Node x l r) = (x : collapse l) ++ collapse r
collapse’ :: Tree a -> [ a ]
collapse’ Nil = []
collapse’ (Node x l r) = collapse’ l ++ (x : collapse’ r)
ex1 :: Tree Integer
ex1 = Node 6 (Node 5 Nil Nil) (Node 3 Nil (Node 17 Nil Nil))
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ Nil = Nil
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)
\end{code}
Values are classified by types, types are classified by kinds.
|Tree| is a \emph{type constructor}.
\begin{code}
data Maybe a = Nothing | Just a
— eliminator, with a pun for b, and a pun for a in ‘Just a’
maybe :: b -> (a -> b) -> Maybe a -> b
maybe b _ Nothing = b
maybe _ f (Just a) = f a
data Either a b = Left a | Right b
either :: (a -> c) -> (b -> c) -> Either a b -> c
either f _ (Left a) = f a
either _ g (Right b) = g b
maybe’ :: a -> Maybe a -> a
maybe’ a = maybe a id
\end{code}
Those two types are very useful to, can be used to, model failing computations.
Some examples:
\begin{code}
hd0 :: [a] -> a
hd0 [] = error “don’t do this!”
hd0 (x:_) = x
hd1 :: [a] -> Maybe a
hd1 [] = Nothing
hd1 (x:_) = Just x
hd2 :: [a] -> Either String a
hd2 [] = Left “Tried to compute the head of an empty string”
hd2 (x:_) = Right x
\end{code}
Write some fun code in Haskell: Edit Distance! The distance between 2 strings,
counting the number of ‘edits’ needed from one to the other.
Ex: fish -> chips
Language of edits:
\begin{code}
data Edit =
Insert Char — don’t move into the string at all
| Change Char — single char
| Copy — single char
| Delete — single char
| Kill — rest of line
run :: Edit -> String -> String
run (Insert c) s = c : s
run (Change _) [] = error “can’t change a character that is not there!”
run (Change c) (_ : s) = c : s
run Copy [] = error “can’t copy a character that doesn’t exist”
run Copy (x : s) = x : s
run Delete [] = error “can’t delete a character that doesn’t exist”
run Delete (_ : s) = s
run Kill _ = []
\end{code}