Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Why does `let map f = id >=> switch f` work in F#?
Asked How to implement map using the fish (>=>, Kleisli composition) operator in F#? a couple of hours ago, and r~~'s answer blew my mind:
let map f = id >=> switch f
It is perfect in its simplicity, but when I look at the type signatures, it is not supposed to work. I've been at it for almost an hour now, so I'm probably missing something fundamental how F# evaluates expressions...
For the record, these are the implementations of bind,switch, and >=>:
let bind
( f : 'a -> Result<'b,'c>)
(result : Result<'a,'c>)
=
match result with
| Ok o -> f o
| Error e -> Error e
let switch
(f : 'a -> 'b)
(x : 'a )
=
f x |> Ok
let (>=>)
(f : 'a -> Result<'b,'error>)
(g : 'b -> Result<'c,'error>)
=
f >> (bind g)
My next attempt was using an alternative implementation for >=>:
let (>=>>)
(f : 'a -> Result<'b,'error>)
(g : 'b -> Result<'c,'error>)
x
=
match (f x) with
| Ok o -> g o
| Error e -> Error e
Here's the test invocation on dotnet fsi:
(id >=>> (switch ((+) 2) : int -> Result<int,string>))
((Ok 27) : Result<int,string>)
//=> Ok 29
I'm already stuck at why >=>> does not blow up on id as its first argument?
This is how I would think evaluation goes, but apparently this is not it:
id >=>> switch ((+) 2)
|
V
(>=>>) id (switch ((+) 2))
|
V
match (id x) with
| Ok o -> (switch ((+) 2)) o
| Error e -> Error e
Note to future self:...
(>=>>) (>=>>)
(f : 'a -> Result<'b,'error>) id
(g : 'b -> Result<'c,'error>) (Ok << ((+) 2) : int -> Result<int,string>))
x ((Ok 27) : Result<int,string>)
(... and make sure to convert a point-free function if it does not make sense at first.)
1 answer
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| toraritte |
Thread: Works for me Thank you again! |
Apr 3, 2024 at 10:11 |
when I look at the type signatures, it is not supposed to work.
The types work because they're parameterized. The types of the combinators involved are (renaming all parameters to be unique for clarity):
id : 'a -> 'a
switch : ('b -> 'c) -> 'b -> Result<'c, 'err>
(>=>) :
('d -> Result<'e, 'err>) ->
('e -> Result<'f, 'err>) ->
('d -> Result<'f, 'err>)
map : ('x -> 'y) -> Result<'x, 'err> -> Result<'y, 'err>
When (>=>) id is type checked, 'd must unify with 'a, and Result<'e, 'err> must also unify with 'a. Since 'a and 'd are currently unknown, this is fine; we simply define them both to be equal to Result<'e, 'err>, with the specialized type of (>=>) now
(>=>) : // (specialized)
(Result<'e, 'err> -> Result<'e, 'err>) ->
('e -> Result<'f, 'err>) ->
(Result<'e, 'err> -> Result<'f, 'err>)
For the second argument, we have switch f, which (inside the definition of map, where f : 'x -> 'y) has type 'x -> Result<'y, 'err>. This is a much simpler match: define 'e to be 'x and 'f to be 'y.
So the final type of id >=> switch f is Result<'x, 'err> -> Result<'y, 'err>, which is exactly what the result of map f should be.
This is how I would think evaluation goes, but apparently this is not it:
id >=>> switch ((+) 2) | V (>=>>) id (switch ((+) 2)) | V match (id x) with | Ok o -> (switch ((+) 2)) o | Error e -> Error e
No, that looks right! Keep going:
match x with
| Ok o -> (switch ((+) 2)) o
| Error e -> Error e
|
V
match x with
| Ok o -> Ok (2 + o)
| Error e -> Error e
which is exactly what map ((+) 2) should do.
Of course the reductions under the match clauses don't happen until that branch is reached, but that doesn't stop us from performing them ahead of time to show that they're equivalent to a different expression.
0 comment threads