I'm learning Haskell using Learn You A Haskell For Great Good!, and I came across this example:
ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650
I thought to myself "well, that 10000
is dying to be parameterized". Using what knowledge I have so far I came up with a solution relying heavily on (.)
and flip
:
flip (takeWhile . flip (<)) (filter odd (map (^ 2) [1..]))
Well, ok we could use >
instead*:
flip (takeWhile . (>)) (filter odd (map (^ 2) [1..]))
Basically, the pointy way of parameterizing out a variable is obvious. No matter where that expression occurs, we can very easily parameterize it out pain-free:
odd_squares n = takeWhile (<n) (filter odd (map (^2) [1..]))
but the point-free way I came up with to just parameterizing out a single variable seems a bit wild, especially the use of flip
twice. At that point you're down in the weeds of things like "which order does (<)
apply again?" and you're losing the entire benefit of pointfree abstraction.
Adding in the sum gives:
sum $ flip (takeWhile . flip (<)) (filter odd (map (^ 2) [1..]))
Many delimiters, a $
, (.)
and flip
.
So, I am guessing that there must be a much easier way of going about parameterizing a variable in a function expression like this. Any hints pointing me in the right direction? I've looked at other posts on stackoverflow which have taken me to https://wiki.haskell.org/Pointfree, but it doesn't help me much since they pick nice clean examples that by pure chance don't require flip
.
Some of the other posts that come up on stackoverflow are more like "hey, make this pointfree for me" requests, and the answers often just go ahead and use a bunch of flips, ending up with unreadable functions. My question is more along the lines of "pointfree is good, you can abstract away data wrangling details, but once you use flip a bunch you're back in the data wrangling weeds, so what other tools are available to help you to pointfree well?"
*Although that's beside the point: if (<)
didn't have a flipped version with another name, we'd have had to flip it, so in general I think the line above is more representative of the process I'm using here and how you'll end up with a bunch of flip
's.
flip
is a fairly low-level tool for writing pointfree code; it’s generally not very readable, especially when the flipped expression is long or there are multiple flips.
Good rules of thumb:
Use a flipped version of an operator instead of flip
if available:
(>)
↔︎ (<)
(>>=)
↔︎ (=<<)
Use a section of a function instead of flip
if it’s still readable:
flip map xs
= (`map` xs)
Use Applicative
combinators to pass arguments as a reader “environment”:
(f <$> g) x = f (g x)
(f <*> g) x = f x (g x)
liftA2 f x y = f <$> x <*> y
For manipulating multiple arguments, wrap them in a tuple and use curry
on the outside to present a normal curried type:
multiplyAdd :: Num a => a -> a -> a -> a
multiplyAdd = fmap curry $ curry
$ (*) <$> fst <*> ((+) <$> fst . snd <*> snd . snd)
Use Arrow
and tuple combinators for manipulating tupled values:
(f *** g) (x, y) = (f x, g y)
(f &&& g) x = (f x, g x)
swap ~(x, y) = (y, x)
both f ~(x, y)
= (f x, f y)
Factor definitions into many small parts
sumOddSquaresLessThan = sum <$> oddSquaresLessThan
where
-- Alternatives:
--
-- * ‘(>)’ instead of ‘flip (<)’
--
-- * ‘flip takeWhile oddSquares <$> …’
-- instead of ‘… <*> pure oddSquares’
oddSquaresLessThan = takeWhile <$> flip (<) <*> pure oddSquares
oddSquares = filter odd squares
squares = map (^ 2) [1 ..]
Here (f <$> g) x
= (f . g) x
= f (g x)
, mapping “under” a parameter (the B combinator); (f <*> g) x = f x (g x)
is applying with a parameter (the S combinator); and pure x y
= const x y
= x
, ignoring the parameter (the K combinator). This is essentially the standard “abstraction algorithm” for converting a lambda-calculus expression to combinator calculus (SKI, BCKW): replace application with S, wrap constants in K, use a parameter with I (identity), and map under a parameter with B.