CODEWITHSUNDEEP
f#
geckos
geckos

Reputation: 6299

How to efficiently create a list in reversed order in F#

Is there anyway to contruct a list in reverse order without having to reverse it

Here is an example, I read all lines from stdin

#!/usr/bin/env dotnet fsi

open System

let rec readLines1 () =
  let rec helper acc =
    match Console.ReadLine() with
    | null -> acc
    | line ->
      helper (line :: acc)
  helper [] |> List.rev

readLines1 () |> List.iter (printfn "%s")

Before return from readLines1 I have to List.rev it so that is in right order. Since the result is a slightly linked list it will have to read all trough it and create the reversed version. Is there any way of creating the list in right order?

Upvotes: 0

Views: 792

Answers (3)

JL0PD
JL0PD

Reputation: 4508

Alternative solution without implementing recursive functions

let lines =
        Seq.initInfinite (fun _ -> Console.ReadLine())
        |> Seq.takeWhile (not << isNull)
        |> Seq.toList

Upvotes: 1

Brian Berns
Brian Berns

Reputation: 17038

You can use a sequence instead of accumulating the lines in a list:

open System

let readLines1 () =
    let rec helper () =
        seq {
            match Console.ReadLine() with
                | null -> ()
                | line ->
                    yield line
                    yield! helper ()
        }
    helper () |> Seq.toList

readLines1 () |> List.iter (printfn "%s")

Upvotes: 4

Tomas Petricek
Tomas Petricek

Reputation: 243096

You cannot create list in reverse order, because that would require mutation. If you read inputs one by one, and want to turn them into a list immediately, the only thing you can do is to create new list, linking to the previous one.

In practice, reversing the list is perfectly fine and that's probably the best way of solving this.

Out of curiosity, you could try defininig a mutable list that has the same structure as immutable F# list:

open System

type MutableList<'T> = 
  { mutable List : MutableListBody<'T> }

and MutableListBody<'T> = 
  | Empty
  | Cons of 'T * MutableList<'T>

Now you can implement your function by mutating the list:

let rec readLines () =
  let res = { List = Empty } 
  let rec helper acc =
    match Console.ReadLine() with
    | null -> res
    | line ->
        let next = { List = Empty }
        acc.List <- Cons(line, next)
        helper next
  helper res

This may be educational, but it's not very useful and, if you really wanted mutation in F#, you should probably use ResizeArray.

Yet another trick is to work with functions that take the tail of the list:

let rec readLines () =
  let rec helper acc =
    match Console.ReadLine() with
    | null -> acc []
    | line -> helper (fun tail -> acc (line :: tail))
  helper id

In the line case, this returns a function that takes tail adds line before the tail and then calls whatever function was constructed before to add more things to the front.

This actually creates the list in the right order, but it's probably less efficient than creating a list and reversing it. It may look nice, but you are allocating a new function for each iteration, which is not better than allocating an extra copy of the list. (But it is a nice trick, nevertheless!)

Upvotes: 3

Related Questions