Defining point-free functions in GHCi
October 27, 2012
While reading a neat article on Haskell, I came upon this example I wanted to try out:
minlist = head . sort
This is a point-free function that composes ‘head’ and ‘sort’ to find the minimum value in a list. The big idea here is that because Haskell evaluates lazily, this doesn’t sort the whole list. That would take O(n log n) time. This function only scans for the minimum value, an O(n) operation. As soon as ‘sort’ produces the first element of the sorted list, it’s done.
I wanted to try this, so I popped open GHCi. You can’t define functions directly in an interactive session, so you use ‘let’:
Prelude> import Data.List
Prelude Data.List> let minlist = head . sort
Unfortunately, it doesn’t work as expected:
Prelude Data.List> minlist [1, 2, 3]
<interactive>:8:10:
No instance for (Num ())
arising from the literal `1'
Possible fix: add an instance declaration for (Num ())
In the expression: `1'
In the first argument of minlist', namely `[1, 2, 3]'
In the expression: minlist [1, 2, 3]
I was puzzled by this error. I became even more puzzled when using minlist’s definition directly did work:
Prelude Data.List> (head . sort) [1, 2, 3]
1
GHCi has a :type command that we can use to show the type of ‘minlist’. Maybe that will help:
Prelude Data.List> :type minlist
minlist :: [()] -> ()
That looks weird. What type are ‘head’ and ‘sort’?
Prelude Data.List> :type head
head :: [a] -> a
Prelude Data.List> :type sort
sort :: Ord a => [a] -> [a]
So ‘head’ takes an array of a’s and returns a single ‘a’. ‘sort’ takes an array of a’s, where ‘a’ is a member of the Ord class, and returns an array of a’s. That makes sense. So we’d expect the type of ‘minlist’ to be:
minlist :: Ord a => [a] -> a
But it’s not. We lost the “Ord a” assertion and instead of [a] -> a, we have [()] -> (). What’s up with that?
With a type annotation, we could explicitly specify the signature above. A little searching turns up a Stack Overflow question on how to annotate types when using ‘let’ in GHCi. It works like this:
Prelude Data.List> let minlist :: Ord a => [a] -> a; minlist = (head . sort)
Did that fix ‘minlist’?
Prelude Data.List> :type minlist
minlist :: Ord a => [a] -> a
Prelude Data.List> minlist [1, 2, 3]
1
It did! So the lesson is when you define a polymorphic function using point-free style, you need an explicit type annotation. Problem solved, and that concludes this episode of me messing around with Haskell.
Edit: Much later, I now discover that minlist = head . sort
requires a type annotation whether or not you’re using GHCi, and this
is in fact due to the monomorphism
restriction.
You can follow me on Mastodon or this blog via RSS.
