合并两个列表

Question

我希望以纯粹的功能方式合并F#中的2个列表.我很难理解语法.

假设我有一个元组 ([5;3;8],[2;9;4])

当我调用该函数时,它应该返回 [5;2;3;9;8;4]

这就是我到目前为止的原因,我确信这是错误的.如果有人能以简单的方式解释,我将不胜感激.

let rec interleave (xs,ys) = function
|([], ys) -> ys
|(x::xs, y::ys) -> x :: y::  interleave (xs,ys) 

Answer 1

你的功能几乎是正确的.let f = function是简写,let f x = match x with所以你不需要明确的args.此外,您的算法需要一些调整.

let rec interleave = function //same as: let rec interleave (xs, ys) = match xs, ys with
  |([], ys) -> ys
  |(xs, []) -> xs
  |(x::xs, y::ys) -> x :: y :: interleave (xs,ys)

interleave ([5;3;8],[2;9;4]) //output: [5; 2; 3; 9; 8; 4]

Answer 2

重要的一点是功能不正确.([1;2;3], [])由于您错过了(xs, [])模式匹配的情况,因此输入失败.此外,参数在咖喱形式中更好,以便更容易与部分应用一起使用.这是更正后的版本:

let rec interleave xs ys =
    match xs, ys with
    | [], ys -> ys
    | xs, [] -> xs
    | x::xs', y::ys' -> x::y::interleave xs' ys'

您可以看到该函数不是尾递归的,因为它(::)在返回递归调用后两次应用cons 构造函数.使尾部递归的一种有趣方法是使用序列表达式:

let interleave xs ys =
    let rec loop xs ys = 
       seq {
             match xs, ys with
             | [], ys -> yield! ys
             | xs, [] -> yield! xs
             | x::xs', y::ys' -> 
                   yield x
                   yield y
                   yield! loop xs' ys'
            }
    loop xs ys |> List.ofSeq