CODEWITHSUNDEEP
haskell
user15553
user15553

Reputation: 301

How do I apply the first partial function that works in Haskell?

Suppose I have a list fns of partial functions from a to b, which I represent as functions from a to Maybe b, and I have an object x of type a. Suppose now that I want to define another function from a to Maybe b which takes the value of the first f x that is not Nothing, if such an f exists in fns, or the value Nothing if no such f exists. So basically it outputs f x for the first f that works, or Nothing if no f works.

It isn't hard to come up with some code that does the job. For example, one can create a list [f x| f <- fns] remove all the Nothings from it, and then take the head of the resulting list, or Nothing if that list is empty. But that feels clumsy, and this seems like the kind of general situation for which there is a much more stylish implementation using some built-in function in Haskell. If so, then I'd be interested to know what it is.

Upvotes: 9

Views: 1052

Answers (3)

MarLinn
MarLinn

Reputation: 319

Warning: This is a really non-standard solution. But I personally really like it for its elegance - and the underlying mind-bending.

On https://wiki.haskell.org/Pointfree you can find a function named swing. Its implementation and type are confusing at first:

swing :: (((a -> b) -> b) -> c -> d) -> c -> a -> d
swing = flip . (. flip id)

You can get a first idea of what it does when you see its fully applied form:

swing f c a = f ($ a) c

In conjunction with other higher-order functions it does things that almost look like magic. Examples from the link:

swing map       :: [a -> b] -> a -> [b]
swing any       :: [a -> Bool] -> a -> Bool
swing foldr     :: b -> a -> [a -> b -> b] -> b
swing zipWith   :: [a -> b -> c] -> a -> [b] -> [c]
swing find      :: [a -> Bool] -> a -> Maybe (a -> Bool)
swing partition :: [a -> Bool] -> a -> ([a -> Bool], [a -> Bool])

All these functions do exactly what you would assume from the types. (But note that the wiki is a little out of date. By now, most of these functions automatically work for any Foldable type.)

The function that you search could start from 

swing mapMaybe :: [a -> Maybe b] -> a -> [b]

and then apply listToMaybe. (Both functions are from Data.Maybe)

A more general form would be

swing mapM :: (Monad m, Traversable t) => t (a -> m b) -> a -> m (t b)

so for example (using the ClassyPrelude for full generality at the cost of some constraint noise, with headMay as a more general form of listToMaybe):

f :: (Traversable t, MonoFoldable (t b), Element (t b) ~ b)
  => t (a -> Maybe b) -> a -> Maybe b
f functions x = join $ headMay <$> swing mapM functions x

Yes, it might turn your head into mush - but it's like bending your head to see a smiley, only with your whole mind.

Upvotes: 4

pigworker
pigworker

Reputation: 43393

In Data.Monoid, a newtype copy of Maybe, called First, has the "take the first Just" behaviour.

If you were looking for a function of type

[a -> First b] -> a -> First b

with the behaviour you describe, it would simply be

fold

from Data.Foldable, because the monoid behaviour for a -> does the pointwise lifting needed: the Monoid for a -> First b is exactly picking the first application outcome whic works. Sadly (for my tears over this have been many), to get Maybe instead of First takes a little more work.

Note that the pointwise lifting, yanking a -> out through [], is just the sort of job for sequenceA, so

(asum .) . sequenceA

will do the job.

It's good to get the monoid structure you need cued from the type: in this case, accessing the Alternative behaviour with asum will have to do.

Upvotes: 9

Alec
Alec

Reputation: 32319

This is what Alternative is for. It represents choice and here you are choosing between Maybe values. You can do something like

foldr (<|>) empty [f x | f <- fns]

In Data.Foldable you also have asum :: (Foldable t, Alternative f) => t (f a) -> f a which does what you want even more directly:

asum [f x | f <- fns]

As a side remark, I should note that MonadPlus also does what you want for its Maybe instance. As in the above, you can have

foldr mplus mempty [f x | f <- fns]

And

msum [f x | f <- fns]

But IMO you should use Alternative here since that more accurately conveys your meaning of "choice".

Upvotes: 12

Related Questions