Fsharpplus: List traverse runs from right to left

[pangwa]

Description

It looks like List.traverse runs from right to left, it should be from left to right according to the document.

Repro steps

Below code could reproduce this problem

let mapper (v: int) =
    Console.WriteLine(sprintf "mapping: %d" v)
    Result.Ok v

let test v =
     List.traverse mapper v |> Result.map List.last

 test [1; 2; 3]

Expected behavior

It should prints

mapping: 1
mapping: 2
mapping: 3

Actual behavior

It prints in the reverse order

mapping: 3
mapping: 2
mapping: 1

Related information

The code runs with FSharpPlus 1.1.6

[pangwa]

Seq.traverse runs in the correct order.

[3Rafal]

So the code for F#+ list traverse is our implementation of Traversable type class:

static member inline Traverse (t:list<_>   ,f , [<Optional>]_output: 'R, [<Optional>]_impl: Traverse) : 'R =
       let cons_f x ys = Map.Invoke List.cons (f x) <*> ys
       List.foldBack cons_f t (result [])

and looks like taken from Haskell's implementation of Traversable list (it even has the same variable name 😉) (source)

instance Traversable [] where
    {-# INLINE traverse #-} -- so that traverse can fuse
    traverse f = List.foldr cons_f (pure [])
      where cons_f x ys = liftA2 (:) (f x) ys

However, in Haskell this code

f1 :: IO Int
f1 = do
  putStrLn "running f1"
  return 1

f2 :: IO Int
f2 = do
  putStrLn "running f2"
  return 2

f3 :: IO Int
f3 = do
  putStrLn "running f3"
  return 3

myResult :: IO [Int]
myResult = traverse id [f1, f2, f3]

will evaluate correctly left-to-right

running f1
running f2
running f3
[1,2,3]

The reason is (IMHO, I may be wrong), that Haskell has a lazy evaluation, so it won't apply function immediatly when running foldr (foldBack in F#).
We could probably fix this by creating lazy versions of foldBack (lazy fold probably doesn't make sense), and using it in our traverse implementation.

[pangwa]

I guess the reason is as you mentioned: haskell is lazy, where it evaluates function parameters lazily. From the Wiki.

Where foldr expands to below in haskell, and it evaluates the left element first because its laziness.

foldr (+) 0 [1..1000000] -->
1 + (foldr (+) 0 [2..1000000]) -->
1 + (2 + (foldr (+) 0 [3..1000000])) -->
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) -->
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) -->
-- ...
-- ...  My stack overflows when there's a chain of around 500000 (+)'s !!!
-- ...  But the following would happen if you got a large enough stack:
-- ...
1 + (2 + (3 + (4 + (... + (999999 + (foldr (+) 0 [1000000]))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + ((foldr (+) 0 []))))...)))) -->

1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + 1000000)...)))) -->
1 + (2 + (3 + (4 + (... + 1999999 ...)))) -->

1 + (2 + (3 + (4 + 500000499990))) -->
1 + (2 + (3 + 500000499994)) -->
1 + (2 + 500000499997) -->
1 + 500000499999 -->
500000500000

[gusty]

Indeed I copied that implementation from Haskell initially and later tried to re-write it with a normal fold (right fold) but for some reason I didn't change it. I think the performance was the same or even worse.

Anyways, I didn't care about the side effect of the mapping function happening in the reverse order, as they are just side effects and not part of the logic, still I agree in that it would be nice to get them in the right order.

[pangwa]

yes, I think it's useful to make it runs in the right order because F# is not a pure functional language. Normally we could use side effect to do other things(e.g. update a variable without introducing another monad.), it might relies the order of traversing.

[gusty]

Sure, but note that it's not a good practice, even in F#, to include sideeffects in let's say a map function call, it's always better and more readable (and less surprising) to use a dedicated iter to perform side-effects. The same applies for traverse.

Anyway, let's try to come up with a solution that fixes the order without compromising performance too much.

[3Rafal]

So I figured out we can probably implement it like this:

open FSharpPlus
open FSharpPlus.Data
open FSharpPlus.Control

let mapTakeWhile f lst =
    let rec loop f acc = function
        | [] -> acc
        | x::xs -> let v = f x
                   if v |> IsLeftZero.Invoke |> not 
                   then loop f (v::acc) xs 
                   else v::acc
    loop f [] lst |> List.rev

let traverseList f (t:list<_>) =
   let mapped = mapTakeWhile f t
   let cons_f x ys =  List.cons <!> x <*> ys
   List.foldBack cons_f mapped (result []) 

and it will run correctly with this example:

let mapper v =
    Console.WriteLine(sprintf "mapping: %d" v)
    if v = 4 then Error "error"
    else Ok v

let result : Result<int,string> = 
    [1..5] 
    |> traverseList mapper 
    |> Result.map List.last

giving result of

mapping: 1
mapping: 2
mapping: 3
mapping: 4
val result : Result<int,string> = Error "error"

We traverse list three times (in worst case), so we get ~O(3n) which is asymptotically equal to previous version.

[pangwa]

So I figured out we can probably implement it like this:

open FSharpPlus
open FSharpPlus.Data
open FSharpPlus.Control

let mapTakeWhile f lst =
    let rec loop f acc = function
        | [] -> acc
        | x::xs -> let v = f x
                   if v |> IsLeftZero.Invoke |> not 
                   then loop f (v::acc) xs 
                   else acc
    loop f [] lst |> List.rev

let traverseList f (t:list<_>) =
   let mapped = mapTakeWhile f t
   let cons_f x ys =  List.cons <!> x <*> ys
   List.foldBack cons_f mapped (result []) 

and it will run correctly with this example:

let mapper v =
    Console.WriteLine(sprintf "mapping: %d" v)
    if v = 4 then Error "error"
    else Ok v

let result : Result<int,string> = 
    [1..5] 
    |> traverseList mapper 
    |> Result.map List.last

giving result of

mapping: 1
mapping: 2
mapping: 3
mapping: 4
val result : Result<int,string> = Ok 3

The result is not correct, I guess? it should be: Error "error" instead of Ok 3

We traverse list twice (in worst case), so we get ~O(2n) which is asymptotically equivalent to previous version.

[3Rafal]

Oops, I made a mistake. Thanks @pangwa
I've edited my example and it should be fine now ;)

[3Rafal]

I guess we can even do it in 2 passes with this version:

let traverseList' f lst =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> let v = f x
                   let consed = List.cons <!> v <*> acc
                   if v |> IsLeftZero.Invoke |> not 
                   then loop consed xs 
                   else consed 
    loop (result []) lst 
    |> Map.Invoke List.rev

What do you think @gusty ?

EDIT:
I've ran simple performance tests:

#time

let ok_f v = Ok v : Result<int,string>
let oldOne = List.traverse ok_f [1..5000000];; 
let newOne = traverseList' ok_f [1..5000000];;

and the results show that this implementation seems to have similar performance

> let newOne = traverseList' ok_f [1..5000000];;;;
Real: 00:00:03.790, CPU: 00:00:03.765, GC gen0: 180, gen1: 53, gen2: 2
> let oldOne = List.traverse ok_f [1..5000000];; ;;
Real: 00:00:05.454, CPU: 00:00:05.875, GC gen0: 220, gen1: 63, gen2: 3

[gusty]

and the results show that this implementation may actually be more performant

@3Rafal then go ahead !