Pergunta
I would like to implement a function that takes as input a size n and a list. This function will cut the list into two lists, one of size n and the rest in another list. I am new to this language and have a hard time learning the syntax.
The main problem I have is that is finding a way to express a size of the list without using any loops or mutable variables.
Can anyone give a me some pointers?
Solução
let split n list =
let rec not_a_loop xs = function
| (0, ys) | (_, ([] as ys)) -> (List.rev xs), ys
| (n, x::ys) -> not_a_loop (x::xs) (n-1, ys)
not_a_loop [] (n, list)
Outras dicas
Let's start with the function's type signature. Since it gets n
and a list as arguments and returns a pair of lists, you have a function split
:
val split : int -> 'a list -> 'a list * 'a list
Here is one approach to implement this function:
let split n xs =
let rec splitUtil n xs acc =
match xs with
| [] -> List.rev acc, []
| _ when n = 0 -> List.rev acc, xs
| x::xs' -> splitUtil (n-1) xs' (x::acc)
splitUtil n xs []
The idea is using an accumulator acc
to hold elements you have traversed and decreasing n
a long the way. Because elements are prepended to acc
, in the end you have to reverse it to get the correct order.
The function has two base cases to terminate:
- There's no element left to traverse (
xs = []
at that point). - You have gone through the first
n
elements of the list (n
decreases to0
at that time).
Here is a short illustration of how split
computes the result:
split 2 [1; 2; 3] // call the auxiliary function splitUtil
~> splitUtil 2 [1; 2; 3] [] // match the 3rd case of x::xs'
~> splitUtil 1 [2; 3] [1] // match the 3rd case of x::xs'
~> splitUtil 0 [3] [2; 1] // match the 2nd case of n = 0 (base case)
~> List.rev [2; 1], [3] // call List.rev on acc
~> [1; 2], [3]
New solution - splitAt is now built into List and Array. See commit around 2014 on github. I noticed this today while using F# in VS.2015
Now you can simply do this...
let splitList n list =
List.splitAt n list
And as you might expect the signature is...
n: int -> list: 'a list -> 'a list * 'a list
Example usage:
let (firstThree, remainder) = [1;2;3;4;5] |> (splitList 3)
printfn "firstThree %A" firstThree
printfn "remainder %A" remainder
Output:
firstThree [1; 2; 3]
remainder [4; 5]
Github for those interested: https://github.com/dsyme/visualfsharp/commit/1fc647986f79d20f58978b3980e2da5a1e9b8a7d
One more way, using fold
:
let biApply f (a, b) = (f a, f b)
let splitAt n list =
let splitter ((xs, ys), n') c =
if n' < n then
((c :: xs, ys), n' + 1)
else
((xs, c :: ys), n' + 1)
List.fold splitter (([], []), 0) list
|> fst
|> biApply List.rev
Here is a great series on folds than you can follow to learn more on the topic.