Haskell: Laziness, Type Class, and Monad

Laziness

A function is strict in an argument if the result is undefined whenever an undefined value is passed to this argument. For instance, (+) is strict in both arguments, while (&&) is strict in its first only. Recall that it is defined by

True && x = x
False && x = False

...

If a function is not strict in an argument, we say that it is non-strict or lazy in that argument.

-- Haskell: The Craft of Function Programming (3e):517

Infinite List

1fibs ::[Integer]
2fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
3take 3 fibs

Mutual Recursion

Unlike OCaml, mutual recursion in Haskell does not need to use let rec (because of laziness).

1isEven :: Int -> Bool
2isEven 0 = True
3isEven n = isOdd (n - 1)
4
5isOdd :: Int -> Bool
6isOdd 0 = False
7isOdd n = isEven (n - 1)

Type Class

1quickSort :: Ord a => [a] -> [a]
2
3quickSort []     = []
4quickSort (x:xs) = quickSort [e|e<-xs,e<=x] ++ [x] ++ quickSort [e|e<-xs, e>x]

Ord is a type class (interface), and [e|e<-xs,e<=x] is list comprehension.

Function signatures defined in type class are similar to overloading in other languages.

1class Eq a where
2  (==) :: a -> a -> Bool

instance of type class is similar to classes implemented interface in other languages.

1instance Monad Maybe where
2    return x = Just x
3    Nothing >>= f = Nothing
4    Just x >>= f  = f x
5    fail _ = Nothing

But what is Monad? Read on.

Monad

Monad is like a box. It keeps tracking of some extra content and makes code cleaner (but not necessary clearer).

Maybe Monad

The Maybe monad chains (>>=) sequences of operations and hides failure handling (extra context) in a monad.

Let's revisit the definition of Maybe from this perspective: (-- starts a comment in Haskell)

1instance Monad Maybe where
2    -- `return` is a function to wrap x as `Just x`.
3    return x = Just x
4    -- As soon as one fails, the rest are ignored and the final result is `Nothing`.
5    Nothing >>= f = Nothing
6    -- Only apply `f` when x is `Just x`， not `Nothing`.
7    Just x >>= f  = f x
8    -- Throw a failure.
9    fail _ = Nothing

Monadic Classes

The type class of Monad is defined as below:

 1class Monad m where
 2    -- core functions of Monad
 3    (>>=)  :: m a -> (a -> m b) -> m b
 4    return :: a -> m a
 5
 6    -- other functions
 7    (>>)   :: m a -> m b -> m b
 8    m >> k = m >>= \_ -> k -- `\_ -> k` is a lambda
 9
10    fail   :: String -> m a
11    fail s = error s

fail is like throw in other languages. Haskell uses it to in pattern matching to enable failure. We do not write them explicitly in code.

>> is a syntax sugar to throw away the result of m a. Thus putStr "foo" >== \_ -> putStr "bar" can be expressed as putStr "foo" >> putStr "bar".

>>= chains tow computations, passing the result of the first computation to the second computation, by wrapping the second computation in a function, and passing the first result as its parameter.

Unlike other languages, in Haskell, return wraps date in a monad.

Let's revisit the definition of Maybe monad under the perspective of monadic class.

1instance Monad Maybe where
2    return :: a -> Maybe a
3    return x = Just x
4    >>= :: Maybe a -> (a -> Maybe b) -> Maybe b
5    Nothing >>= f = Nothing
6    Just x >>= f  = f x
7    fail :: String -> Maybe a
8    fail _ = Nothing

Do Notation

1helloWorld :: IO ()
2helloWorld =
3    do
4        putStr "Hello"
5        putStr " "
6        putStrLn "world!"

Haskell syntax is layout sensitive, in other words, it conforms to offside rule. Although Haskell does support braces and semicolons, this alternative style is rare in the Haskell community.

do { putStr "Hello"; putStr " "; putStrLn "world!"; }

Within a do notation, <- binds the result to a name.

1echo :: IO ()
2echo =
3    do
4        line <- getLine
5        putStrLn line

In fact, do notation is an alternative syntax for monad:

1putStr "Hello" >> putStr " " >> putStrLn "world!"
2
3echo :: IO ()
4echo = getLine >>= putStrLn