## HPR2788: Looping in Haskell

## Manage episode 231001711 series 108988

Haskell is functional language where data is immutable. This means that regular for-loops don’t really exist. Looping however is very common pattern in programs in general. Here are some patterns how to do that in Haskell.

## Recursion

Calculating Fibonacci numbers is common example (sort of like hello world in Haskell). There’s many different implementations at https://wiki.haskell.org/The_Fibonacci_sequence if you’re interested on having a look.

Simple recursive definition:

`fibs :: Integer -> Integer fibs 0 = 0 fibs 1 = 1 fibs n = fibs (n-1) + fibs (n-2)`

When called with `0`

result is `0`

. When called with `1`

result is `1`

. For all other cases, `fibs`

is called with values `n-1`

and `n-1`

and the results are summed together. This works fine when `n`

is small, but calculation gets slow really quickly with bigger values.

Another way is to define list of all Fibonacci numbers recursively:

`allFibs :: [Integer] allFibs = 0 : 1 : zipWith (+) allFibs (tail allFibs)`

Here a list is constructed. First element is `0`

, second element is `1`

and rest of the list is obtained by summing the list with its tail (everything but the first element of the list). Definition is recursive and defines all Fibonacci numbers. However, Haskell doesn’t evaluate whole list, but only as much of it as is required.

Common pattern of processing elements in a list, producing a new list:

`addOne :: [Integer] -> [Integer] addOne [] = [] addOne (x:xs) = x + 1 : addOne xs`

Two cases, when called with an empty list `[]`

, result is empty list. For all other cases, list is taken apart `(x:xs)`

, `x`

contains first element of the list and `xs`

is rest of the list. Body of the function creates a new list where head is `x + 1`

and tail is `addOne xs`

. This processes whole list of `Integer`

by adding one to each value. It also reverses the list.

Second common pattern is processing a list and reducing it to a single value:

`sumAll :: Integer -> [Integer] -> Integer sumAll n [] = n sumAll n (x:xs) = sumAll (n + x) xs`

If given list is empty (the terminal case), result is `n`

. Second case again takes list apart `(x:xs)`

, adds `x`

and `n`

together and recursive call `sumAll`

with tail of the list.

This common pattern is discarding some elements of a list:

`evenOnly :: [Integer] -> [Integer] evenOnly [] = [] evenOnly (x:xs) = if even x then x : evenOnly xs else evenOnly xs`

Again, result of empty list is just empty list. In all other cases we first check if `x`

is even. If so, new list is constructed where head is `x`

and tail is `evenOnly xs`

. If `x`

isn’t even, it’s discarded and `evenOnly`

is called recursively with tail of the list.

## More tools

Writing recursion by hand gets tedious and sometimes confusing (if you listened to the show, you probably noticed how I got confused and had to check that `evenOnly`

actually works as I thought it would). For that reason, there are tools that abstract these common patterns and given them names.

First is `map`

. It applies given function to each element of a list, thus producing a new list:

`> map (+1) [1..10] [2, 3, 4, 5, 6, 7, 8, 9, 10, 11] > map odd [1..10] [True, False, True, False, True, False, True, False, True, False]`

Second is `fold`

. There is good article at https://wiki.haskell.org/Foldr_Foldl_Foldl%27 that talks about differences between different folds.

The basic idea behind each fold is the same, they take a function and initial value and then apply them to first element of list, producing a value. This value is then applied with the function to the second element of the list and so on, until whole list has been reduced to a single value. Calculating a sum of list is so common operation that there’s specific function for that: `sum`

.

`> foldr (+) 0 [1..10] 55 > foldl (+) 0 [1..10] 55 > sum [1..10] 55`

`scan`

is similar to `fold`

, except for returning only the final value, it also returns intermediate ones. Here it’s easier to observe how `scanr`

and `scanl`

differ from each other:

`> scanr (+) 0 [1..10] [55,54,52,49,45,40,34,27,19,10,0] > scanl (+) 0 [1..10] [0,1,3,6,10,15,21,28,36,45,55]`

Last of the trifecta is `filter`

that is used to select some of the elements in a list based on a supplied function.

`> filter odd [1..10] [1, 3, 5, 7, 9] > filter even [1..] [2, 4, 6, 8, 10, 12, 14, 16...] > take 5 $ filter even [1..] [2, 4, 6, 8, 10]`

## Even more tools

There are even more tools at our disposal. Prelude is basic library of Haskell and browsing online documentation at http://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html might yield interesting information.

For example, constructing some lists:

`iterate :: (a -> a) -> a -> [a]`

For list where function is applied repeatedly.`repeat :: a -> [a]`

for a list that contains infinite amount of`a`

.`replicate :: Int -> a -> [a]`

For a list that contains finite amount of`a`

.`cycle :: [a] -> [a]`

For a infinite list that repeats same list over and over again.

## Finding tools

It’s all about knowing the right tools and finding them when needed. Luckily, you don’t have to memorize big stack of notes, but can turn to https://hoogle.haskell.org/ which is Haskell API search engine. It can search based on name or type signature. I often use it to find out if somebody has already written a function that I’m thinking of writing myself.

If you want to send questions or comments, I can be reached with email or at fediverse where I’m tuturto@mastodon.social. This episode is direct result of feedback that I got from previous one. If there’s Haskell topic you would love to hear more, drop me line or even better, research it by yourself and make a cool Hacker Public Radio episode.

2835 episodes available. A new episode about every day .