# Mark Needham

Thoughts on Software Development

## Haskell: Chaining functions to find the middle value in a collection

I’ve been playing around with writing merge sort in Haskell and eventually ended up with the following function:

```1 2 3 4 5 6 7 8 9 10 11 12 msort :: [Int] -> [Int] msort unsorted = let n = floor (fromIntegral(length unsorted) / 2) in if n == 0 then unsorted else let (left, right) = splitAt n unsorted in merge (msort left) (msort right) where merge [] right = right merge left [] = left merge left@(x:xs) right@(y:ys) = if x < y then x : merge xs right else y : merge left ys```

The 3rd line was annoying me as it has way too many brackets on it and I was fairly sure that it should be possible to just combine the functions like I learnt to do in F# a few years ago.

It’s pretty easy to do that for the first two functions ‘length’ and ‘fromIntegral’ which we can do like this:

`middle = fromIntegral . length`

The third line now reads like this:

`let n = floor ((middle unsorted) / 2)`

It’s a slight improvement but still not that great.

The problem with working out how to chain the division bit is that our value needs to be passed as the first argument to ‘/’ so we can’t do the following…

`middle = ((/) 2) . fromIntegral . length`

…since that divides 2 by the length of our collection rather than the other way around!

```> middle [1,2,3,4,5,6] 0.3333333333333333```

Instead we want to create an anonymous function around the ‘/’ function and then apply floor:

```middle :: [Int] -> Int middle = floor . (\y -> y / 2) . fromIntegral . length```

And merge sort now looks like this:

```msort :: [Int] -> [Int] msort unsorted = let n = middle unsorted in if n == 0 then unsorted else let (left, right) = splitAt n unsorted in merge (msort left) (msort right) where merge [] right = right merge left [] = left merge left@(x:xs) right@(y:ys) = if x < y then x : merge xs right else y : merge left ys```

Which I think is pretty neat!

Be Sociable, Share!

Written by Mark Needham

March 20th, 2012 at 11:36 pm

Tagged with

• One trick I’ve seen to avoid needing the anonymous function to work around argument order is the `flip` function, which reverses the order of arguments a function takes.

So you could rewrite `middle` as:

```middle = floor . flip (/) 2 . fromIntegral . length
```

For me (a Haskell newbie) that’s harder a bit harder to follow, but as flipping arg order seems to crop up quite frequently with function composition it is probably worth knowing about. 🙂

Cheers,
David

• David Turner

Hi Mark,

The function (y -> y/2) can be written as (/ 2) which is called a ‘section’ in the literature. It’s the same as (flip (/) 2) as David Tchepak used in his comment. Note that putting parentheses around an infix function (as in (/)) turns it into a normal function which is used in prefix position, which is why ((/) 2) and (/ 2) are not the same thing. Just to add to the confusion, ((/) 2) is the same as (2 /) which is the other section of (/).

You may be interested to install ‘hlint’, available on hackage, which is good for suggesting ways that your code could become more idiomatic Haskell. If you run hlint on a program containing (y -> y/2) it will say ‘why not (/2)?’

Cheers,

David T

• David Turner

Oh yes, and (floor . (/ 2) . fromIntegral) is probably better written as (n -> n div 2) or, using a section, simply (`div` 2). I think you’re after integer division which is written ‘/’ in many languages, but we don’t have that kind of overloading in Haskell.

• Thanks for pointing that out, that’s much nicer. That’s the problem I have with Haskell/FP; it always seems so obvious to me after someone points it out. 🙂 < runsOffToPracticeMore />

• @8ba6e5de7bc28c280457a075f599677d:disqus I’ve been wondering what the difference was between ‘div’ and ‘/’ and couldn’t figure it out so thanks for pointing that out!

• @8ba6e5de7bc28c280457a075f599677d:disqus didn’t know about hlint so I’ll give that a try, should be interesting to see what it comes up with!

The section stuff sounds interesting as well, will take a look at that.

Thanks for showing me some cool ways to improve the code!

• David Turner

Are you using GHCi? If so, do you know about the ‘:t’ command?

Prelude> :t (/)
(/) :: Fractional a => a -> a -> a
Prelude> :t div
div :: Integral a => a -> a -> a

• @8ba6e5de7bc28c280457a075f599677d:disqus yeh I’ve been using ghci…I guess what I meant was that I didn’t realise they had different signatures – I’d incorrectly assumed they were interchangeable from looking at some code samples!
‘:t’ is cool though, thanks for pointing it out.