Mark Needham

Thoughts on Software Development

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

with 8 comments

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!

Written by Mark Needham

March 20th, 2012 at 11:36 pm

Posted in Haskell

Tagged with

«
»
  • http://davesquared.net David Tchepak

    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.

  • http://davesquared.net David Tchepak

    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 />

  • http://www.markhneedham.com/blog Mark Needham

    @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!

  • http://www.markhneedham.com/blog Mark Needham

    @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

  • http://www.markhneedham.com/blog Mark Needham

    @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.