Archive

Archive for December, 2016

Code kata – a final note

The last two posts discussed how to solve the first problem out of five provided on this page. For completeness, I provide my answers to the other problems as well. The code is more standard functional programming (where haskell shines ofcourse but it leaves no surprises I guess).

Categories: Uncategorized

Some code kata – haskell while loops

In the previous post we solved the following problem using a for loop

Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.

I have not found while loop primitives in the standard library but a library for this exists on hackage and it is called Control.Monad.Loops. It provides the following implementation

whileM_ :: (Monad m) => m Bool -> m a -> m ()
whileM_ p f = go
  where go = do
           x <- p
           if x
           then f >> go
           else return ()

Looking at the type signature we see that it takes a bool wrapped in a monad as a first argument and another monad which is the action as a second argument. The result, as with the for loop, is a monad containing nothing (or more correct the unit value).

Again, since we want to do stateful programming we will turn to the State monad. This time we need to keep both the remaining list and the sum within the state. A tuple seems like a natural choice.

The most complicated part is the condition. We use the get function to retrieve the current state. The get function has the following type signature

get :: MonadState s m => m s

It simply returns the state as a value wrapped within the monad. However, we want to test wether the list is empty or not. fmap or the equivalent applicative functor <$> is a function that allow us to apply an ordinary function to the value wrapped within the monad – transforming it to something else which in this case should be a boolean value indicating whether we should continue looping or not.

This is the type signature for fmap and <$> respectivly

(<$>) :: Functor f => (a -> b) -> f a -> f b
fmap :: Functor f => (a -> b) -> f a -> f b

To test whether the list is empty we can then do the following (assuming that the list is stored as the first element in the state tuple)

not . null . fst <$> get

The final result, when putting this together, may look like below

import Control.Monad
import Control.Monad.State

whileM_ p f = go
  where go = do
    x <- p
    if x
    then f >> go
    else return ()

sumUsingWhile xs = snd $ execState loop (xs,0)
  where
    loop = whileM_ (not . null . fst <$> get) $
             modify $ \(x:xs,sum) -> (xs, x+sum)

 

Categories: Uncategorized

Some code kata – haskell for loops

First of all – read and enjoy solving these small puzzle problems.

I also did that but with a little twist – I picked haskell which makes the first problem a bit more challenging. Why? Because for and while loops requires mutable states which is something that is not supported by haskell. Unless… you turn to monads and more specifically the state monad.

Lets repeat problem 1:

Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.

In the standard library Control.Monad we can actually find primitives for for-loops. The one that I used is called forM_ and has the type signature

forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()

The first argument is a foldable type t which is similiar to enumerable in .net. It is generic so any item of type a might be enumerated.

The second argument is the action that we want to repeatadly invoke. It takes as an argument an element of the enumerable. It returns a monad containing a value of some type b. Do not worry too much about what a monad is right now just hang on.

The result is a monad without a value (or for purists: the only value of the unit type). This indicates that the result of the forM_ function is only side effects. Side effects within the monad that is.

The standard monad for side effects is the State monad. To execute a state monad and actually get a result the following function is provided

execState :: State s a -> s -> s

It takes a state monad and an initial state and returns the resulting state.

Last, but not least, we need to be able to modify the state.

modify :: MonadState s m => (s -> s) -> m ()

Using this function we can pass a function that takes the current state as input and returns the new state.

Putting the pieces together we get

import Control.Monad
import Control.Monad.State

sumUsingFor xs = execState loop 0
    where
        loop = forM_ xs $ \x -> modify (+x)

I think that is pretty impressive for a language that does not support mutable states.

Next time, we will have a look at the while loop implementation.

Categories: Uncategorized