CODEWITHSUNDEEP
f#
Trident D'Gao
Trident D'Gao

Reputation: 19762

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

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?

Upvotes: 10

Views: 4216

Answers (4)

J D
J D

Reputation: 48697

Append x to xs like this:

xs @ [x]

Note that this is O(n).

Upvotes: 4

TooTone
TooTone

Reputation: 8146

Referring back to your original code, I think what you are looking for is to use List.foldBack rather than List.fold. Essentially, foldBack repeatedly applies the folder function starting from the end of the list rather than from the start of the list. It's not as efficient as fold but it's better to use foldBack and avoid reversing the list.

With foldBack, your accumulation function folder is applied to a list x0::x1::...::xlast as follows, where the initial argument to folder isinit:

folder x0 (folder x1 ( ... (folder xlast init) ... ) )

c.f. fold

folder (... (folder (folder init x0) x1) ...) xlast

There are some other answers to your original question that suggest alternative solutions, but sticking with your code, substituting foldBack for fold results in a first implementation 

let chunkOrig items chunkSize =
    let folder =
        fun x (result, chunk) ->
            if List.length chunk < chunkSize then
                (result, x::chunk)
            else
                (chunk::result, [x])
    let (a,b) = List.foldBack folder items ([], []) 
    b::a

Already this is a lot simpler, as all the list reversing has gone. And it seems to work.

> chunkOrig [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]

However when your list doesn't divide into equal chunks it goes wrong, because foldBack starts from the last element.

> chunkOrig [1..11] 2;;
val it : int list list = [[1]; [2; 3]; [4; 5]; [6; 7]; [8; 9]; [10; 11]]

What you need to do is parameterise your local function folder by the length remaining in the current chunk rather than by the chunk itself.

let chunk items chunkSize =
    let folder =
        fun x (result, lenLeft) ->
        if lenLeft > 0 then
            match result with
               | [] -> ([[x]], lenLeft-1)
               | r0::rtail -> ((x::r0)::rtail, lenLeft-1)
        else
            ([x]::result, chunkSize-1)
    let (result, lenLeft) = List.foldBack folder items ([], (List.length items) % chunkSize) 
    result

> chunk [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]

> chunk [1..11] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]; [11]]

Upvotes: 3

pad
pad

Reputation: 41290

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

Upvotes: 5

Tomas Petricek
Tomas Petricek

Reputation: 243096

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.

Upvotes: 9

Related Questions