f# foldback: Does accumulator need to be the same as list type?

Question

I have the following code. I have spent a lot of time trying to figure out why it complains about the second argument to my List.foldback function. It complains that it wants "acc" to be (char * bool * (Direction -> int * int) * int). This does not make any sense to me because the documentation shows that it simply matches the 'State. In this case, I am trying to make the 'State a "Movement list".

For a full description of what I am doing, please visit the Code golf voronoi problem

type Direction = Left=0 | Up=1 | Right=2 | Down=3
type Movement = (char * (int * int) * Direction)

let rec masterClaims (items:Movement list) =
    items

    // Execute these methods in the order in which they are passed. 
    |> List.map (fun (ch, coord, dir) -> 
        (
            ch,
            // This function does the claiming. This has to be 
            // done in the order of the input list. 
            claimCells ch coord,
            getCoordinate coord,
            int dir
        ))

    // Create next items and fold them into the final results for the layer. 
    // Use foldback so that they are pre-pended to the final list in the correct
    // order.
    |> List.foldBack (fun (ch, wasClaimed, getCoordinate, directionInt) (acc:Movement list) ->           
        if (wasClaimed) then

            // Create a list of next nodes to inspect
            // [counter-clockwise; forward; clockwise]
            [(directionInt+3)%4;directionInt;(directionInt+1)%4]
            |> List.map enum<Direction>
            |> List.iter (fun direction ->
                (
                    ch, 
                    getCoordinate direction, 
                    direction
                ) :: acc |> ignore)

        acc // should be  Movement list
        ) List.empty<Movement>


    // The theory here is that we will execute the fold
    // for every item before we pass the entire collection
    // to the recursive call. 
    |> masterClaims

The code with Tomas' fix

let inline foldBackNormal f s input = List.foldBack f input s 

type Direction = Left=0 | Up=1 | Right=2 | Down=3
type Movement = (char * (int * int) * Direction)

let rec masterClaims (items:Movement list) =
    items

    // Execute these methods in the order in which they are passed. 
    |> List.map (fun (ch, coord, dir) -> 
        (
            ch,
            // This function does the claiming. This has to be 
            // done in the order of the input list. 
            claimCells ch coord,
            getCoordinate coord,
            int dir
        ))

    // Create next items and fold them into the final results for the layer. 
    // Use foldback so that they are pre-pended to the final list in the correct
    // order.
    |> foldBackNormal (fun (ch, wasClaimed, getCoordinate, directionInt) (acc:Movement list) ->           
        if (wasClaimed) then

            // Create a list of next nodes to inspect
            // [counter-clockwise; forward; clockwise]
            [(directionInt+3)%4;directionInt;(directionInt+1)%4]
            |> List.map enum<Direction>
            |> List.iter (fun direction ->
                (
                    ch, 
                    getCoordinate direction, 
                    direction
                ) :: acc |> ignore)

        acc // should be  Movement list
        ) List.empty<Movement>


    // The theory here is that we will execute the fold
    // for every item before we pass the entire collection
    // to the recursive call. 
    |> masterClaims

Answer 1

The List.foldBack function is a bit odd in that it takes the input list as the argument before the last one and the initial state as the last argument. So switching the order of the last two arguments should fix the problem. Alternatively, you can define a helper with switched order of arguments and use that:

let foldBackNormal f s input = List.foldBack f input s

This is for historical reasons (compatibility with OCaml), but I'm sure you're not the only one who finds this confusing :-).