hpr2788 :: Looping in Haskell
tuturto describes some loop-like constructs in Haskell
Hosted by tuturto on Wednesday 2019-04-10 is flagged as Clean and is released under a CC-BY-SA license.
Tags: haskell, programming.
Listen in ogg, spx, or mp3 format. | Comments (0)
Part of the series: Haskell
A series looking into the Haskell (programming language)
A series looking into the Haskell (programming language)
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.
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 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 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
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.
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.
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]
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:
> 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
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 https://hackage.haskell.org/package/base-184.108.40.206/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
replicate :: Int -> a -> [a]For a list that contains finite amount of
cycle :: [a] -> [a]For a infinite list that repeats same list over and over again.
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 firstname.lastname@example.org. 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.
Automatically generated using whisper
<< First, < Previous, Next >, Latest >>
whisper --model tiny --language en hpr2788.wav