Function Composition Do Notation

Question

Is there a "do notation" syntactic sugar for simple function composition?

(i.e. (.) :: (b -> c) -> (a -> b) -> a -> c)

I'd like to be able to store results of some compositions for later (while still continuing the chain.

I'd rather not use the RebindableSyntax extension if possible.

I'm looking for something like this:

composed :: [String] -> [String]
composed = do
    fmap (++ "!!!")
    maxLength <- maximum . fmap length
    filter ((== maxLength) . length)

composed ["alice", "bob", "david"]
-- outputs: ["alice!!!", "david!!!"]

I'm not sure something like this is possible, since the result of the earlier function essentially has to pass "through" the bind of maxLength, but I'm open to hearing of any other similarly expressive options. Basically I need to collect information as I go through the composition in order to use it later.

Perhaps I could do something like this with a state monad?

Thanks for your help!

Edit

This sort of thing kinda works:

split :: (a -> b) -> (b -> a -> c) -> a -> c
split ab bac a = bac (ab a) a

composed :: [String] -> [String]
composed = do
    fmap (++ "!!!")
    split 
        (maximum . fmap length)
        (\maxLength -> (filter ((== maxLength) . length)))

Crosshead

Please specify what composition you're actually trying to obtain here. At the very least, give the type signature you want for composed! – Oiler

Just normal function composition, but with the ability to store interstitial results for use in later function calls (see the example). I added the type. – Crosshead

Is there a reason you need to write it in point-free style? This should be easy in non-point-free style. – Turnabout

@immibis I suppose I could split some of the functions a bit. This example is simplified however, in my actual use-case I'm re-using one of the earlier values like 6 or 7 function calls later and I'm not sure how I'd make that clean. Do you have an example of how this would help out? – Crosshead

Something along the lines of composed xs = filter ((== maxLength) . length) modified where modified = fmap (++ "!!!") xs maxLength = maximum $ fmap length modified (with appropriate whitespace) – Turnabout

Answer 1

As leftaroundabout mentioned, you can use Arrows to write your function. But, there is a feature in ghc Haskell compiler, which is proc-notation for Arrows. It is very similar to well-known do-notation, but, unfortunately, not many people aware of it.

With proc-notation you can write your desired function in next more redable and elegant way:

{-# LANGUAGE Arrows #-}

import Control.Arrow (returnA)
import Data.List     (maximum)

composed :: [String] -> [String]
composed = proc l -> do
    bangedL <- fmap (++"!!!")        -< l
    maxLen  <- maximum . fmap length -< bangedL
    returnA -< filter ((== maxLen) . length) bangedL

And this works in ghci as expected:

ghci> composed ["alice", "bob", "david"]
["alice!!!","david!!!"]

If you are interested, you can read some tutorials with nice pictures to understand what is arrow and how this powerful feature works so you can dive deeper into it:

https://www.haskell.org/arrows/index.html

https://en.wikibooks.org/wiki/Haskell/Understanding_arrows

Pyroxylin

Good to mention, though I'd say the strength of proc notation is that it allows you to write quite general arrow compositions as if they were functions in lambda syntax. If the category you're working on is (->), then there's not much reason to not just use lambdas / let...in binding to accomplish the same thing, if you're going to give those intermediate results names anyway. – Oiler

@Oiler Yes, there exist arrows besides (->) and you may want to write general version function compositions though I didn't do it for this case to make example simpler. Your version follows thoughts from this blog-post: degoes.net/articles/insufficiently-polymorphic But sometimes having variable names may ease code understandability (especially for arrows). – Pyroxylin

Answer 2

One possible way to achieve something like that are arrows. Basically, in “storing interstitial results” you're just splitting up the information flow through the composition chain. That's what the &&& (fanout) combinator does.

import Control.Arrow

composed = fmap (++ "!!!")
       >>> ((. length) . (==) . maximum . fmap length &&& id)
       >>> uncurry filter

This definitely isn't good human-comprehensible code though.

A state monad would seem to allow something related too, but the problem is that the state type is fixed through the do block's monadic chain. That's not really flexible enough to pick up different-typed values throughout the composition chain. While it is certainly possible to circumvent this (amongst them, indeed, RebindableSyntax), this too isn't a good idea IMO.

Oiler

Hrmm, Interesting! I gave something similar a try in the edit above, I'd still love to see something a bit more elegant though, it's all a bit awkward :/ – Crosshead

Answer 3

The type of (<*>) specialised to the function instance of Applicative is:

(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)

The resulting r -> b function passes its argument to both the r -> a -> b and the r -> a functions, and then uses the a value produced by the r -> a function as the second argument of the r -> a -> b one.

What does this have to do with your function? filter is a function of two arguments, a predicate and a list. Now, a key aspect of what you are trying to do is that the predicate is generated from the list. That means the core of your function can be expressed in terms of (<*>):

-- Using the predicate-generating function from leftaroundabout's answer.
maxLengthOnly :: Foldable t => [t a] -> [t a]
maxLengthOnly = flip filter <*> ((. length) . (==) . maximum . fmap length)

composed :: [String] -> [String]
composed = maxLengthOnly . fmap (++ "!!!")

This maxLengthOnly definition would be a quite nice one-liner if the pointfree predicate-generating function weren't so clunky.

Since the Applicative instance of functions is equivalent in power to the Monad one, maxLengthOnly can also be phrased as:

maxLengthOnly = (. length) . (==) . maximum . fmap length >>= filter

(The split you added to your question, by the way, is (>>=) for functions.)

A different way of writing it with Applicative is:

maxLengthOnly = filter <$> ((. length) . (==) . maximum . fmap length) <*> id

It is no coincidence that this looks a lot like leftaroundabout's solution: for functions, (,) <$> f <*> g = liftA2 (,) f g = f &&& g.

Finally, it is also worth noting that, while it is tempting to replace id in the latest version of maxLengthOnly with fmap (++ "!!!"), that won't work because fmap (++ "!!!") changes the length of the strings, and therefore affects the result of the predicate. With a function that doesn't invalidate the predicate, though, it would work pretty well:

nicerComposed = filter
    <$> ((. length) . (==) . maximum . fmap length) <*> fmap reverse

GHCi> nicerComposed ["alice","bob","david"]
["ecila","divad"]

Goya

Answer 4

What you have is essentially a filter, but one where the filtering function changes as you iterate over the list. I would model this not as a "forked" composition, but as a fold using the following function f :: String -> (Int, [String]):

1. The return value maintains the current maximum and all strings of that length.
2. If the first argument is shorter than the current maximum, drop it.
3. If the first argument is the same as the current maximum, add it to the list.
4. If the first argument is longer, make its length the new maximum, and replace the current output list with a new list.

Once the fold is complete, you just extract the list from the tuple.

-- Not really a suitable name anymore, but...
composed :: [String] -> [String]
composed = snd . foldr f (0, [])
    where f curr (maxLen, result) = let currLen = length curr
                                    in case compare currLen maxLen of
                                       LT -> (maxLen, result)       -- drop
                                       EQ -> (maxLen, curr:result)  -- keep
                                       GT -> (length curr, [curr])  -- reset

Farinaceous