If i have an entry x and a list of functions x -> Opt[x], what is the idiomatic functional programming way to apply each of the functions successively to get a resulting Opt[x]?
x -> [x->Opt[x]] -> Opt[x]
Each x -> Opt[x] is some sort of filtering/enriching function, which can either add stuff to x or return nothing if it wants to filter x.
I know the usual suspects like Optional and List monads and their map, apply and bind functions, but i am having a hard time coming up with a solution which feels functional programming idiomatic.
Thank you for any clue into the right direction!
Bergi's answer is simple and works, so if you're using Haskell or know how to translate foldM to your language of choice, that's probably going to be the easiest way to do it.
If you're interested in a more generalisable way to think about this problem, however, read on.
I'm going to translate the desired function into Haskell. I'm assuming that
x -> [x->Opt[x]] -> Opt[x]
is the same as
a -> [a -> Maybe a] -> Maybe a
in Haskell.
The first thing we might notice is that a pattern starts to emerge if we rearrange the terms a bit:
[a -> Maybe a] -> a -> Maybe a
Because of currying, that is equivalent to:
[a -> Maybe a] -> (a -> Maybe a)
The brackets are redundant, so they're only for illustrative purposes. Continuing the didactic line for a moment, suppose we introduce a type alias:
type Foo a = a -> Maybe a
The above type would now be:
[Foo a] -> Foo a
So the question is now of a recognisable abstract form of which 'we' know the answer: How do we reduce an arbitrary list of values to a single value?
This is possible if the values in the list give rise to a monoid. Specifically in Haskell, this function is mconcat, which generalises to fold.
This is fun!
The question is, now, does a -> Maybe a give rise to a monoid?
That function type is really a Kleisli arrow: Kleisli Maybe a a. Is there a Monoid instance for Kleisli arrows? Yes, at least three.
We may notice that Kleisli Maybe a a looks like an endomorphism because of the repeated a. It's not quite an endomorphism, but perhaps we can make it one...
Monadic bind with the arguments flipped (=<<) will turn a function foo of the type a -> Maybe a into an endomorphism:
ghci> :t (=<<) foo
(=<<) foo :: Integral b => Maybe b -> Maybe b
Almost there. Now wrap it in Endo to make it a Monoid instance:
ghci> :t Endo $ (=<<) foo
Endo $ (=<<) foo :: Integral a => Endo (Maybe a)
We're going to need a few functions to play with:
projectEven i = if even i then Just i else Nothing
foo i = if i `mod` 10 == 0 then Just (i + 1) else Nothing
We can now make a list of these:
ghci> :t [foo, projectEven]
[foo, projectEven] :: Integral a => [a -> Maybe a]
Map them all to that Monoid instance:
ghci> :t fmap (Endo . (=<<)) [foo, projectEven]
fmap (Endo . (=<<)) [foo, projectEven]
:: Integral a => [Endo (Maybe a)]
fold it:
ghci> :t fold $ fmap (Endo . (=<<)) [foo, projectEven]
fold $ fmap (Endo . (=<<)) [foo, projectEven]
:: Integral a => Endo (Maybe a)
and unwrap it:
ghci> :t appEndo $ fold $ fmap (Endo . (=<<)) [foo, projectEven]
appEndo $ fold $ fmap (Endo . (=<<)) [foo, projectEven]
:: Integral a => Maybe a -> Maybe a
That's a function from Maybe a to Maybe a. Since we want a -> Maybe a, we can compose it with Just so that the 'normal' a is lifted to Maybe a:
ghci> :t (appEndo $ fold $ fmap (Endo . (=<<)) [foo, projectEven]) . Just
(appEndo $ fold $ fmap (Endo . (=<<)) [foo, projectEven]) . Just
:: Integral a => a -> Maybe a
Let's make that a function:
runFilters = (appEndo $ fold $ fmap (Endo . (=<<)) [foo, projectEven]) . Just
That's just a normal function that you can call:
ghci> runFilters 10
Just 11
ghci> runFilters 20
Just 21
ghci> runFilters 2
Nothing
ghci> runFilters 3
Nothing
Clearly, this isn't as easy as foldM, but may perhaps hint at some deeper abstractions at play.
Really, I just got a bit carried away here, sorry...