Breadcrumb Tutorial - Haskell

So,  what's a breadcrumb?

Breadcrumbs lead you through learning a language. Breadcrumbs demonstrate language features, complement tutorials, help you check your understanding as you go, and are a way to quickly get a feel for the style and syntax of the language. Breadcrumbs are food for thought.

* If you're learning the language, we especially encourage you to open up a REPL and play around with the code! *


If you're not sure how to type up and run this code in Haskell, see How to learn Haskell, especially this note.



Hello World
-- the canonical hello world example
main = do
    putStrLn "Hello World!"

Infinity
{- Lazy evaluation in Haskell allows
   for cool things, like the definition
   of infinite lists!
-}

{-The following code segments construct lists.
They do so by giving the first term and something from which a pattern can be gathered.
The '..' means to continue the pattern until the end term is reached.
If there is no given end term, the list constructed will be an infinite list.
-}

naturals = [1..]
--This constructs an infinite list with the first term of 1,
--the pattern being that the next term will be 1+ the previous list term (the default pattern).

even_numbers = [0,2..]
--This constructs an infinite list with the first two terms of 0 and 2.
--Between these first two terms, a pattern of adding 2 to each successive term is noted.
--The rest of the list is constructed using this pattern, adding 2 to each term to get the next.

even_numbers' = map (*2) naturals
--This function maps the operation (*2) to the list naturals,
--constructing a list where each value is 2 times that of the corresponding value in naturals.

odd_numbers = map (+1) even_numbers
--This function maps the operation (+1) to the list even_numbers,
--constructing a list in which each value is one more than that of the corresponding value in even_numbers.


List Comprehensions
-- an alternate way of expressing lists

naturals = [ x | x <- [1..] ]

perfect_squares = [ x*x | x <- naturals ]

multiples_of_3 = [ x | x <- naturals, x `mod` 3 == 0 ]

all_pairs = [ (x,y) | x <- [1..10], y <- [1..10] ]


Currying
-- partial application of functions

add a b = a+b

add3 = add 3

multiples_of n = [n,n*2..]

multiples_of_43 = multiples_of 43


Lists
lst   = 1 : 2 : 3 : 4 : []
lst'  = [1,2,3,4]
lst'' = 1 : [2,3,4]

foo  = [1,2] ++ [3,4]
foo' = [1,2,3] ++ [4]

inf_ones   = 1 : inf_ones
inf_ones'  = [1,1..]
inf_ones'' = [1] ++ inf_ones

first lst = head lst
rest lst  = tail lst

nth_index n lst = lst !! n
last lst = lst !! (length lst)

10_elems lst = take 10 lst
11_and_beyond lst = drop 10 lst


Advanced Infinite Lists
-- a bit of a challenge maybe, but you should understand this before you get too deep
fib = 1 : 1 : map (\(a,b) -> a + b) (zip fib (tail fib))

Composition
import Data.List (sort)

min_n n = (take n) . sort

descending_sort lst = (reverse . sort) lst


Function Application Operator
-- the name is scary, the actual thing is not

add = (+)  -- (+) is the way to refer to the + as a regular (not special & infix) function
divide = (/)

foo = add 2 (divide 4 5)
foo' = add 2 $ divide 4 5

{-
the idea is that blah $ foo bar baz is shorthand for blah (foo bar baz)
it's a way to save parenthesis :-)
-}




Pattern Matching
fact 0 = 1
fact n = n * fact (n-1)

len [] = 0
len lst = 1 + len (tail lst)

len' [] = 0
len' (x:xs) = 1 + len xs

foo "hello" = "asdf"
foo "world" = "BALOONS"
foo _       = "CHUNKY BACON"


At Patterns
foo allxs@(x:xs) = "All xs are: " ++ (show allxs) ++ "\n"
                   ++ "The first x is: " ++ (show x) ++ "\n"
                   ++ "The rest of the xs are: " ++ (show xs)

{- usage (ghci):
*Main> putStrLn $ foo [1,2,3,4]
All xs are: [1,2,3,4]
The first x is: 1
The rest of the xs are: [2,3,4]
-}




Guards
-- guards are a lot like pattern matching
foo n | n < 0 = "negative"
      | n == 0 = "zero"
      | otherwise = "positive"


Case
foo n = case signum n of 
	(-1) -> "negative"
	0 -> "zero"
	1 -> "positive"


Where

max_list lst = head rslst where
    rslst = reverse slst
    slst = sort lst

chocolate pie = delicious pie where
    delicious = (++) "your mom's "


Tuples

min_max_list lst = (head slst, head rslst) where
    rslst = reverse slst
    slst = sort lst

magnitude (x,y) = sqrt (x^2 + y^2)

pythagorean_triples = [(a,b,c) | c <- [1..],
                                 a <- [1..c],
                                 b <- [a..c],
                                 a^2 + b^2 == c^2]


Rpn
-- ignore the parts that haven't been explained yet, and come back to it later
-- the things to ignore are noted

rpn :: String -> [Int] -- ignore this
rpn str = foldr stackSolve [] (reverse (words str)) -- you probably don't know what foldr means yet (but you might!)
  where stackSolve :: String -> [Int] -> [Int]
        stackSolve [] _ = []
        stackSolve word stack = case word of
          "+" -> binOp (+) stack
          "-" -> binOp (-) stack
          "*" -> binOp (*) stack
          "/" -> binOp div stack
          "%" -> binOp mod stack
          _   -> (read word) : stack
        binOp _ [] = error "Stack underflow (0 items on stack, binOp)"
        binOp _ (x:[]) = error "Stack underflow (1 item on stack, binOp)"
        binOp f (x:y:xs) = ((flip f) x y) : xs   -- flip takes a function of two arguments and reverse their order
     
              

Lambdas
-- we can define functions on the fly with lambas
-- their use will make more sense later on


foo f x y = f x y
callFoo = foo (\a b -> a + b) 1 2 
-- we define an anonymous function that 
-- takes arguments a and b, and adds them together
-- and we call it right away with arguments 1 and 2


-- a good example uses map from the standard library, which
-- applies a function to everything in a list
addOneToEverything lst = map (\a -> a + 1) lst



Closures
-- using closures to make "objects"
num a = \cmd b -> case cmd of
                     "plus" -> a + b
                     "minus" -> a - b
                     "times" -> a * b
                     "divided by" -> a / b

{- gchi session: -------------

*Main> let three = num 3
*Main> three "plus" 2
5.0
*Main> three "times" 11
33.0


Data
-- This makes a Vector type that has three Int-type fields
data Vector = ConstructorName Int Int Int

 -- the constructor name can be the same as the type name if we want
data Vec = Vec Int Int Int

-- we can also have multiple constructors
-- note that the constructor really determines a lot more about
-- the structure than a "constructor" does in C++/Java
data PolyVec = R2 Int Int           -- R2 is the set of points in the plane, but we're using it as the name of a constructor for 2d vectors
             | R3 Int Int Int       -- R3 is 3d space
             | R4 Int Int Int Int  


-- we can pattern match of data types to extract their fields
-- also, notice how on the left (ConstructorName x y z) is a pattern match
-- while on the right, it's actually calling the constructor like a function to return a new Vector
vectorPlus (ConstructorName a b c) (ConstructorName d e f) = (ConstructorName (a+d) (b+e) (c+f))


-- this function is identical to the constructor function that the data statement generates for us
makeVector x y z = ConstructorName x y z

-- we could even write
makeVector' = ConstructorName


-- lastly an example of pattern matching on PolyVec constructors
project (R2 x y) = R3 x y 0
project (R3 x y z) = R4 x y z 0


Enumerated Types
data EnumeratedType = Foo | Bar | Baz

func Foo = "Got a foo!"
func Bar = "Got a bar!"
func Baz = "Got a baz!"

func' enum = case enum of
               Foo -> "Got a foo!"
               Bar -> "Got a bar!"
               Baz -> "Got a baz!"

decide n | n < 0 = Foo
         | n == 0 = Bar
         | otherwise = Baz
             
run = func . decide
run' = func' . decide
{- example usage in ghci:
run (-1)   -- you need the parens to distinguish the negative number from a partial application of the (-) function
run 0
run 1
run 10

Type
-- every function has a type
add :: Int -> Int -> Int
add a b = a + b


-- in general, this is more like the following (not valid haskell code)
foo :: InputType -> OutputType

-- or for a function of five arguments (as an example)
bar :: InputType1 -> InputType2 -> InputType3 -> InputType4 -> InputType5 -> OutputType

-- or a function of no arguments!
baz :: OutputType


-- for instance
name = "Joe Schmoe" -- this is a function! really!

Type Classes
-- a type class in Haskell is a bit like an interface in Java
--(think of a as a type-parameter, like the Foo in "public class Blah implements Comparable<Foo>"


-- the below is simplified, but valid
class Mathy a where
  add :: a -> a -> a
  times :: a -> a -> a
  


-- now we can make data types that are instances of Num, meaning they have to implement the functions that Num specifies

data Vector = Vector Int Int Int
instance Mathy Vector where
    add (Vector a b c) (Vector x y z) = Vector (a+x) (b+y) (c+z)
    times (Vector a b c) (Vector x y z) = Vector (a*x) (b*y) (c*z) -- this isn't real vector multiplication but who cares






Type Classes Again
-- here we give our class a type parameter
class Useless a where
    func :: a -> String
    func arg = ""  -- we also give it a (not-very-helpful) default implementation

data Thing = Thing String Int
instance Useless Thing -- since we have a default func, we don't have to specify one



-- lastly, there are a lot of built in type classes
data Pair = Pair Int Int

-- An example is Show; things that are instanced of show
-- can be turned into Strings

-- a quick example of using Show (the method show forces things to implement is called "show")
-- notice that the numbers are instances of Show and we use that to turn them into strings here
pairToString (Pair x y) = "(" ++ (show x) ++ "," ++ (show y) ++ ")"


-- now that we have a function to turn pairs into strings we can actually just make pair an instance of Show
instance Show Pair where
    show = pairToString


-- now we could say
turnMyPairIntoAString pair = show pair
-- or
aPairAsAString = show (Pair 23 14)




The Other Meaning Of Type
type Name = String
-- this aliases Name to be a special kind of String


-- for instance:
whatsMyName :: Name  -- remember type specifications?
whatsMyName = "Sasquatch"




More Currying
-- all of these are equivalent!
f a b = a + b
f' a = \b -> a + b
f'' = \a b -> a + b
f''' = \a -> \b -> a + b


Newtype As A Wrapper
-- try to understand this, it's a pretty common pattern when using and defining some monads

newtype State s a = State { runState :: (s -> (a,s)) } 


Bind
{- >>= is often called "bind" and is one of the required functions in the Monad typeclass -}


f >>= g
-- is equivalent to
do
   a <- f
   g a
-- and to
 f >>= (\a -> g a)

-- and also that
f >> g
-- is equivalent to
_ <- f
g
-- and to
f >>= (\_ -> g)


List Monad
-- things that are equivalent because of list monad behavior
map (+1) [1,2,3,4]
liftM (+1) [1,2,3,4]




List Monad Two
-- equivalent due to the list monad

[1,2,3] >>= \x -> ([4,5,6] >>= \y -> return (x,y))
concatMap (\x -> concatMap (\y -> [(x,y)]) [4,5,6]) [1,2,3]

Custom State Monad
-- Based on the code at the Gentle Introducton to Haskell tutorial
-- here: http://www.haskell.org/tutorial/monads.html

type S = String

data SM a = SM (S -> (a,S))  -- The monadic type

instance Monad SM where
  -- defines state propagation
  SM c1 >>= fc2         =  SM (\s0 -> let (r,s1) = c1 s0 
                                          SM c2 = fc2 r in
                                         c2 s1)
  return k              =  SM (\s -> (k,s))

 -- extracts the state from the monad
readSM                  :: SM S
readSM                  =  SM (\s -> (s,s))

 -- updates the state of the monad by applying 'f'
updateSM                :: (S -> S) -> SM ()  -- alters the state
updateSM f              =  SM (\s -> ((), f s)) 

-- run a computation in the SM monad
runSM                   :: S -> SM a -> (a,S)
runSM s0 (SM c)         =  c s0




doSomething = do
	updateSM ((flip (++)) " world")
	
main = do
	let (_, thing) = runSM "hello" doSomething
	putStrLn thing

Statet
-- Taken verbatim from: http://www.haskell.org/pipermail/libraries/2005-April/003558.html
-- Thanks, "isaac"

import Control.Monad.State

type MyState a = StateT Int IO a

stateFun :: MyState String
stateFun = do 
  modify (+100)
  liftIO (putStrLn "Hello!")
  return "foo"

main = do
  (s, n) <- runStateT (stateFun >> stateFun) 0
  putStrLn $ "n: " ++ (show n) ++ " s: " ++ s