Haskell


http://www.haskell.org/

What is Haskell?

Haskell is a purely functional, non-strictly (lazy) evaluated programming language with a strict static type system based on Hindley-Milner type inference.

There appears to be a lot of Haskell/Scheme overlap. Schemers would do well to learn the language of and learn about Haskell.

Haskell's inheritance

Haskell has a very elegant syntax, a program or script is a set of declarations. While in Scheme the main data type is a symbolic expression, Haskell has algebraic data types.

Lisp, the predecessor of Scheme born as a system to compute with primitive recursive symbolic functions. Primitive recursive functions is an important subject in computation theory, to study what kind of functions are computable. The primitive recursive functions are build to operate on natural numbers. John McCarthy introduced lists playing the role of natural numbers. Cons is analog to Successor, Nil is analog to Zero, etc. And everything even the functions are Symbolic expressions.

Haskell has a different genesis, it also has Lisp in it's genealogy, but is part of a functional languages that are based on Lambda calculus and Combinatory Logic with types. It has more influence of John Backus FP/FFP system, and Milners ML. John Backus (the creator of Fortran) in his Turing dissertation 1978, proposed functional programming as a way to solve the Von Neumann bottle neck (assignment) with some ideas from K.Iverson's APL. He also proposed FFP a system of functional forms. That means to have more use of higher order functions, like fold. ML was the Meta-Language program verification system. It was written with formal verification in mind.

While ML has assignment instructions, Haskell does not. To compute states, it takes structures from Category Theory. Although one can learn to program in Haskell without knowing any category theory, it is important to learn the concepts to develop a better approach to structure and design programs. The main category used in Haskell is called Monad.

Programming in Haskell

To give an idea of how a Haskell program is, lets study the factorial function which all the schemers love:

(define (fact n)(if (= 0 n) 1 (* n (fact (- n 1))))

translated to Haskell

fact n = if 0==n then 1 else n * fact (n - 1)

great, there are other ways to write it in Haskell. One way is to use pattern matching.

fact   0   = 1
fact (n+1) = (n+1) * fact n

If fact 5 is evaluated the 5 is taken as (((((0+1)+1)+1)+1)+1, which is close to Peano's notation for the natural number 5: s(s(s(s(s(0))))). The first equation matches the case for 0, while the second for every number greater than 0.

McCarthy understood that the naturals could be extended with symbolic expressions. being equally computable, so Lisp was a Turing complete programming language, that means that Lisp's computational power is the same of a Turing machine, primitive recursive functions, Lambda calculus, etc.

5 could be represented in Lisp as (cons 1 (cons 1 (cons 1 (cons 1 (cons 1 0))))) which is pretty printed as (1 1 1 1 1 . 0) it has the same structure than (s s s s s . 0). Although that seems wrong because cons : SExp X Lists -> Lists and 0 is not a list, Nil is a list, (but a correct SExp in Lisp). Then 5 could be represented as list by (cons 1 (cons 1 (cons 1 (cons 1 (cons 1 Nil))))) playing Nil the role of 0.

Haskell also has lists, cons is represented by the infix operator ":" and Nil is represented by "[]". The list 1:(2:(3:[]))) is pretty printed as [1,2,3] like (1.(2.(3.Nil))) in Scheme. 1:(2:3) is not legal in Haskell because 3 is a number not a list of numbers.

The selectors car and cdr can be defined in Haskell as follows:

car (x:xs) = x
cdr (x:xs) = xs

they are called head and tail in Haskell, but pattern matching is used more often.

Lets go to the point to see other way to compute the factorial. The 5! = 1x1x2x3x4x5 = 120 one way to compute it is to compute the product of the numbers in the list: [1,2,3,4,5] which can be abbreviated in Haskell writing [1..5], the program to compute the product of a list of numbers in Haskell is:

prod   []   = 1
prod (x:xs) = x * prod xs

with that function we can define the factorial function as follows:

fact n = prod [1..n]

The [m..n] could be defined in Scheme as follows:

(define (fromTo m n) 
    (if (< m n) (cons m (fromTo (+ 1 m) n) 
                (if (= m n) (cons n nil) nil)))

To compute 5! one compute 1x2x3x4x5x1 product is commutative and associative, so that computes the same result. To compute 1x1x2x3x4x5 we could write a tail recursive version:

prod' xs = h 1 xs
  where h n [] = n
        h n (x:xs) = h (n*x) xs

Suppose that we want to sum the numbers in a list:

sum   []   = 0
sum (x:xs) = x + sum xs

or the tail recursive version:

sum' xs = h 0 xs
  where h n [] = n
        h n (x:xs) = h (n+x) xs

prod and sum have the same structure, prod' and sum' too.

We can have functions as parameters, why we don't write a program generalizing the structure, the first computes associating to the right, the tail recursive associates to the left, so they are called foldr and foldl respectively.

foldr op e xs   = h xs
   where h   []   = e
         h (x:xs) = op x (h xs)

and

foldl op e xs = h e xs
   where h e   []   = e
         h e (x:xs) = h (op e x) xs

Now we can write factorial either as:

fact n = foldr (*) 1 [1..n]

or

fact n = foldl (*) 1 [1..n]

When we compute fact 5 it computes fold (*) 1 (1:(2:(3:(4:(5:[]))))) which computes (1*(2*(3*(4*(5*1))))) it is replacing every cons operator ":" by a times operator "*" and "[]" by "1". if you studied a course on modern algebra, you can remember that such relation among two algebraic structures, is called an homomorphism.

That is an important issue, because the fold functions are not just a generalization of the structure of sum and prod, it allow us to define homomorphisms.

The fold function is called reduce in other languages, it eats the list like a catabolism, for that reason such morphisms are called catamorphisms.

That is an intellectual improvement, because we can think more abstractly. Let's see for example, how map can be defined in terms of foldr

map apply a function to each member of a list, it's type is:

map ::  (a -> b) -> [a] -> [b]

that means that the first argument is a function from a to b and the second is a list of a, giving as a result a list of b. The recursive definition of map is:

map f [] = []
map (x:xs) = f x : map f xs

but we can define it in terms of foldr as follows:

map f xs = foldr op [] xs
   where op x y = f x : y

Other functions are append (called "++" in Haskell,)

append :: [a] -> [a] -> [a]
append xs ys = foldr (:) ys xs

and

concat :: [[a]] -> [a]
concat xs = foldr append [] xs

use:

append [1,2,3] [4,5,6]       ----> [1,2,3,4,5,6]
concat [[1],[2,3],[4,5],[6]] ----> [1,2,3,4,5,6]

Other features of Haskell

Haskell also has Lambda expressions, the combinators of SKI calculus, I called id, K called const, can be defined using lambda expressions as follows:

id = \ x -> x
const = \x y -> x
s = \ f g x -> f x (g x)

although thay are defined in Haskell's prelude

id             :: a -> a
id    x         = x
const          :: a -> b -> a
const k _       = k

you can verify that SKK=I (the comments are written within "{-" and "-}" braces.)

(\f g x -> f x (g x))(\x y -> x)(\x y -> x)
= {- subst f/(\x y -> x) -}
(\g x -> (\x y -> x) x (g x))(\x y -> x)
= {-subst g/(\x y -> x) -}
(\x -> (\x y -> x) x ((\x y -> x) x))
= {- reduce (\x y -> x) x ((\x y -> x) x)) -}
(\x -> x)

Also observe that (\x->E x) == E called eta-conversion, for that reason concat can also be defined as follows:

concat = foldr append []

that makes more easy to compose functioms

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

with the given definitioms you can check the following property of map:

map f . map g == map (f . g)

Conclusion

Those schemers who want to learn Haskell should keep in mind that they should think more algebraically their programs. They can adopt the same structure in Scheme, but Haskell has a more elegant syntax.

Try to learn more about the functional forms used in Haskell (many are also included in Scheme).

Although this article does not yet covers data types, that is an important issue too. A good exercise is to define a fold function for trees, here is a definition of a tree structure:

data Tree a = Leaf a | Fork (Tree a)(Tree a)

Try to make more use of higher order functions in Scheme and other programming languages too. Some like C are limited, because functions can not return functions, but one can pass function pointers as arguments.

I can't say Scheme or Hasekll to be better, they are different and I use both, depending on what I want to do, I could even include C as other important language that every programmer should learn, as well as Prolog. All are formative.