Make Fish in F#

Question

The Kleisli composition operator >=>, also known as the "fish" in Haskell circles, may come in handy in many situations where composition of specialized functions is needed. It works kind of like the >> operator, but instead of composing simple functions 'a -> 'b it confers some special properties on them possibly best expressed as 'a -> m<'b>, where m is either a monad-like type or some property of the function's return value.

Evidence of this practice in the wider F# community can be found e.g. in Scott Wlaschin's Railway oriented programming (part 2) as composition of functions returning the Result<'TSuccess,'TFailure> type.

Reasoning that where there's a bind, there must be also fish, I try to parametrize the canonical Kleisli operator's definition let (>=>) f g a = f a >>= g with the bind function itself:

let mkFish bind f g a = bind g (f a)

This works wonderfully with the caveat that generally one shouldn't unleash special operators on user-facing code. I can compose functions returning options...

module Option =
    let (>=>) f = mkFish Option.bind f
    let odd i = if i % 2 = 0 then None else Some i
    let small i = if abs i > 10 then None else Some i
    [0; -1; 9; -99] |> List.choose (odd >=> small)
    // val it : int list = [-1; 9]

... or I can devise a function application to the two topmost values of a stack and push the result back without having to reference the data structure I'm operating on explicitly:

module Stack =
    let (>=>) f = mkFish (<||) f
    type 'a Stack = Stack of 'a list
    let pop = function
    | Stack[] -> failwith "Empty Stack"
    | Stack(x::xs) -> x, Stack xs
    let push x (Stack xs) = Stack(x::xs)
    let apply2 f =
        pop >=> fun x ->
        pop >=> fun y ->
        push (f x y)

But what bothers me is that the signature val mkFish : bind:('a -> 'b -> 'c) -> f:('d -> 'b) -> g:'a -> a:'d -> 'c makes no sense. Type variables are in confusing order, it's overly general ('a should be a function), and I'm not seeing a natural way to annotate it.

How can I abstract here in the absence of formal functors and monads, not having to define the Kleisli operator explicitly for each type?

Answer 1

You can't do it in a natural way without Higher Kinds.

The signature of fish should be something like:

let (>=>) (f:'T -> #Monad<'U>``) (g:' U -> #Monad<'V>) (x:'T) : #Monad<'V> = bind (f x) g

which is unrepresentable in current .NET type system, but you can replace #Monad with your specific monad, ie: Async and use its corresponding bind function in the implementation.

Having said that, if you really want to use a generic fish operator you can use F#+ which has it already defined by using static constraints. If you look at the 5th code sample here you will see it in action over different types.

Of course you can also define your own, but there is a lot of things to code, in order to make it behave properly in most common scenarios. You can grab the code from the library or if you want I can write a small (but limited) code sample.

The generic fish is defined in this line.

I think in general you really feel the lack of generic functions when using operators, because as you discovered, you need to open and close modules. It's not like functions that you prefix them with the module name, you can do that with operators as well (something like Option.(>=>)) , but then it defeats the whole purpose of using operators, I mean it's no longer an operator.