Tags: /
haskell
/
(Based on a class taught by a teacher of mine.)
Haskell is a purely functional programming language.
There are no statements. Only expressions. For a discussion about the difference between the two, see here.
This means a function cannot change the value of any of its parameters. They can only return values.
There are no side effects. Each expression is sort of self-contained. Whatever happens in an expression cannot affect other unrelated expressions.
So it's possible, and often helpful, to think of a Haskell program as simply a set of equations.
(No wonder mathematicians like functional programming languages like Haskell :D)
We can 'store equations' into variables in a sense. This is possible Haskell does lazy evaluation. The equation won't be evaluated till it is needed.
Let's see a few built-in functions in Haskell which can help us in our venture.
zipWithzipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Combines two lists by applying a function to their elements position-wise. The size of the resultant list is min(len(list1, list2)).
Examples:
> zipWith (+) [1,2,3] [1,2]
[2,4]
> zipWith (*) [2,3] [4,5,6]
[8,15]
> zipWith (*) [2,3,4] [5,6,7,8]
[10,18,28]
> zipWith (-) [2,3,4] [5,6,7,8]
[-3,-3,-3]
tailtail :: [a] -> [a]
Returns everything except the first element of a list.
Passing an empty list to tail would cause exception.
> tail []
*** Exception: tail: empty list
> tail [1]
[]
> tail [1,2,3,4]
[2,3,4]
taketake :: Int -> [a] -> [a]
Accepts an integer (n) along with a list and returns the first n elements of the list.
> take 2 [1,2,3,4]
[1,2]
> take 3 [1,2,3,4]
[1,2,3]
> take 10 [1..100]
[1,2,3,4,5,6,7,8,9,10]
Now that we have seen the built-in Haskell functions we'll use, let's make the Fibonacci series.
The 'equation' for the Fibonacci series may be written as:
fibo = 1 : 1 : zipWith (+) fibo (tail fibo)
Here, a list is being made. The first two elements are explicitly given (1 and 1) and the remaining elements are found based on that.
The zipWith (+) fibo (tail fibo) part basically takes two 'copies' (not really copies) of fibo, removes the first element from one of them with tail fibo and adds elements of fibo and tail fibo position-wise.
The result is the list of Fibonacci numbers.
It works something like this:
fibo : 1 1 ... | 1 1 2 ... | 1 1 2 3 ... | 1 1 2 3 5 ...
tail fibo: 1 ... | 1 2 ... | 1 2 3 ... | 1 2 3 5 ...
--------- → ---------- → ------------ → --------------
zipWith : 2 | 2 3 | 2 3 5 | 2 3 5 8
fibo denotes the infinite list of Fibonacci numbers. But thanks to lazy evaluation, its expansion is done only to the extent that is asked for.
Getting the first 10 Fibonacci numbers is as easy doing:
> take 10 fibo
[1,1,2,3,5,8,13,21,34,55]
And we can use list indexing syntax of Haskell (ie, !!) to get the i-th Fibonacci number.
fibo !! i
where indexing starts from zero.
> fibo !! 3
3
> fibo !! 13
377
> fibo !! 15
987
> fibo !! 150
16130531424904581415797907386349
Neat, isn't it? And this is basically just a single-line program!