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!

http://davesquared.net David Tchepak

David Turner

David Turner

http://davesquared.net David Tchepak

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

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

David Turner

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