У меня есть список в F#, который выглядит так:
let x = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3]
Мне нужно написать функцию, которая возвращает элементы списка, которые идут раньше и включают два последовательных 0. Он должен вернуться:
[10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]
Это было бы довольно легко сделать в цикле for на нефункциональном языке, но каков правильный функциональный подход к этому?
Не существует единственного «правильного» решения, но вот решение, в котором вместо рекурсии используются встроенные функции:
let snip list =
list
|> List.pairwise
|> List.takeWhile (fun pair ->
pair <> (0, 0))
|> List.map fst
|> fun list' -> list' @ [0; 0]
let x = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3]
snip x
|> printfn "%A" // [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]
Или, если вам нравится безточечный стиль, вы можете сделать так:
let flip f b a = f a b
let snip =
List.pairwise
>> List.takeWhile ((<>) (0, 0))
>> List.map fst
>> flip List.append [0; 0]
Если вы изучаете fp, вы можете предпочесть делать это напрямую (нет ничего плохого в том, чтобы делать это напрямую).
let x = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3]
let rec find : int list -> int list = function
| 0 :: 0 :: _ -> [ 0; 0 ]
| head :: tail -> head :: find tail
| _ -> []
let foo = find x
и получить
val foo: int list = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]
Помимо прямого решения с использованием рекурсии и функции pairwise
, вот одно решение с использованием общей функции fold
, которое выглядит вполне читабельно:
x |> Seq.fold (fun (res, zs) el ->
if zs = 2 then res, zs
elif el = 0 then el::res, zs+1
else el::res, 0 ) ([], 0) |> fst |> List.rev
Идея состоит в том, чтобы сохранить собранные до сих пор элементы (res
) и количество нулей, увиденных до текущего элемента (zs
). Как только число достигает 2, мы игнорируем остальную часть списка (это все еще повторяется по остальной части списка, поэтому могут быть некоторые накладные расходы).
Можно также посмотреть на проблему с другой стороны.
Итерировать список в обратном порядке и отбрасывать элементы, виденные до сих пор, если встречаются два последовательных нуля, или возвращать весь список в противном случае.
([10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3], [])
||> List.foldBack (fun x -> function
| 0::xs when x = 0 -> 0::0::[]
| xs -> x::xs )
// val it : int list = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]
Мне нравится этот!
Используйте рекурсию для итерации по списку, вырываясь из функции, когда вы видите свой второй 0.