How do I append to a list in F# rather than prepend?

Question

Prepending to a list in F# is somewhat annoying because once you're done you have to reverse it. Is there a way to build a list straight from start?

Answer 1

There is nothing wrong with prepending and reversing the list. You can use append (@) on a single-element list, but it is a code smell. A tolerable (tail-recursive) approach is:

let appendSingle xs x =
    [ yield! xs
      yield x ]

All the above solutions have O(n) execution time. For your use case, you could keep a private ResizeArray to avoid the use of reverse. It is fine since mutability is hidden. Compare this function

let filter f l = 
  let rec loop acc l =
    match l with 
    | [] -> List.rev acc                        
    | x::xs when f x -> loop (x::acc) xs  
    | x::xs -> loop acc xs
  loop [] l

with its more efficient counterpart

let filter f l = 
  let rec loop (acc : ResizeArray<_>) l =
    match l with 
    | [] -> Seq.toList acc                        
    | x::xs when f x -> 
        acc.Add(x)  
        loop acc xs  
    | x::xs -> loop acc xs
  loop (ResizeArray()) l

Answer 2

If you need to append elements to the end, you can use the type known as DList. There is an implementation available in FSharpX.

However, there is some runtime overhead associated with this (e.g. see the comments here) and so I think that building list by prepending and then reversing is generally going to be more efficient. It is also quite standard thing to do in functional programming - it may look a bit confusing at first, but it is a very common "design pattern" when implementing recursive functions that walk over lists, so I would not try to avoid it.