Intro to Haskell ADTs

ADT.hs

module ADT where

import Prelude hiding (Bool, True, False,
                       negate, and, or,
                       List, Cons, Nil,
                       Maybe, Just, Nothing,
                       Either, Left, Right,
                       Tree, Node, Leaf)

-- Simplest ADT

data Bool = True | False
  deriving Show

negate :: Bool -> Bool
negate True = False
negate False = True

and :: Bool -> Bool -> Bool
and True True = True
and _ _ = False

or :: Bool -> Bool -> Bool
or True _ = True
or _ True = True
or _ _ = False

-- We can make many common data structures, this is actually how Haskell
-- represents a list internally

data List a = Cons a (List a) | Nil
  deriving Show

toList :: List a -> [a]
toList Nil = []
toList (Cons a as) = a : toList as

mapList :: (a -> b) -> List a -> List b
mapList f Nil = Nil
mapList f (Cons a as) = Cons (f a) (mapList f as)

-- Another useful type defined by the prelude is Maybe, it represents a value
-- that may not be present

data Maybe a = Just a | Nothing
  deriving Show

head :: List a -> Maybe a
head Nil = Nothing
head (Cons a as) = Just a

-- The power of ADTs is to be able to express more complex data structures

-- A tree element is either a node that contains two sub-trees or a leaf that
-- contains some data

data Tree a = Node (Tree a) (Tree a) | Leaf a
  deriving Show

example1 :: Tree Int
example1 = Leaf 22

example2 :: Tree Int
example2 = Node (Leaf 1) (Leaf 2)

example3 :: Tree Int
example3 = Node example2 example1

flatten :: Tree a -> [a]
flatten (Leaf x) = [x]
flatten (Node l r) = flatten l ++ flatten r