Sure, pretty much anything can be made pointfree. The tricky thing is what functions you'll allow in the resulting expression. If we pattern match, we generally need a fold function to do the matching instead. So, for instance, if we pattern matched on a Maybe a
, we'd need to replace that with maybe
. Similarly, Either a b
patterns can be written in terms of either
.
Note the pattern in the signatures
data Maybe a = Nothing | Just a
maybe :: b -> (a -> b) -> (Maybe a -> b)
Maybe a
has two constructors, one which takes no arguments and the other which takes an a
. So maybe
takes two arguments: one which is a 0-ary function (b
), and one which takes an a
(a -> b
), and then returns a function from Maybe a -> b
. The same pattern is present in either
data Either a b = Left a | Right b
either :: (a -> c) -> (b -> c) -> (Either a b -> c)
Two cases. The first takes an a
and produces whatever c
we want. The second takes a b
and produces whatever c
we want. In every case, we want one function for each possible term in the sum type.
In order to systematically pointfree a function like \[x] -> x
, we'd need a similar fold. [a]
is declared as, essentially
data [a] = [] | a : [a]
So we'd need a function with this signature
list :: b -> (a -> [a] -> b) -> ([a] -> b)
Now, flip foldr
comes close
flip foldr :: b -> (a -> b -> b) -> ([a] -> b)
But it's recursive. It calls its provided function on the [a]
part of a : [a]
. We want a true fold, which isn't provided by Haskell's base libraries. A quick Hoogle search tells us that this function does exist in a package though, called extra
. Of course, for this small example we can just write it ourselves very easily.
list :: b -> (a -> [a] -> b) -> ([a] -> b)
list f g x = case x of
[] -> f
(y:ys) -> g y ys
Now we can apply it to your \[x] -> x
easily. First, let's write what your function really does, including all of the messy undefined
cases (I'll use undefined
rather than a long error message here, for brevity)
func :: [a] -> a
func x = case x of
[] -> undefined
(y:ys) -> case ys of
[] -> y
(_:_) -> undefined
Now every case statement exactly matches each constructor once. This is ripe for transformation into a fold.
func :: [a] -> a
func x = case x of
[] -> undefined
(y:ys) -> list y undefined ys
And now we transform the outer case as well
func :: [a] -> a
func x = list undefined (\y -> list y undefined) x
So we have
func :: [a] -> a
func = list undefined (\y -> list y undefined)
Or, if we want to be truly crazy about it
func :: [a] -> a
func = list undefined (flip list undefined)
But this function isn't in base
Yeah, that's true. We kind of cheated by using a fold that didn't exist. If we want to do it systematically, we need that fold operator. But without it, we can still kludge it together with foldr1
, which suffices for our particular purposes.
func' :: [a] -> a
func' = foldr1 (const (const undefined))
So, to answer your question, we can't always systematically replace pattern matching like in your example with pointfree, unless we have a fold function with the right signature. Fortunately, that function can always be written, for any Haskell 98 data type (possibly GADTs as well, but I haven't considered that possibility in any depth). But even without that support, we can still make it work, kind of.