在 F# 中合并有序列表，期待一个 'a 但给定一个 'a -> a' 列表

Question

我正在尝试在 F# 中实现合并排序，因为我正在尝试学习函数式编程。但是我运行遇到了这个辅助功能合并的问题。希望有人能指出我正确的方向。请记住，我对 F# 只有基本的了解。

let rec merge a b =
match a, b with
|q, [] -> q
|[], p -> p 
|q::q', p::p' when q<p -> q::merge q' p::p'
|q::q', p::p' when p<q -> p::merge q::q' p';;

merge [1;3;5;7;9] [2;4;6;8;10];;

控制台输出：

Uge2.fsx(96,34): error FS0001: Type mismatch. Expecting a
'a    
but given a
'a list    
The resulting type would be infinite when unifying ''a' and ''a list'
> 

Uge2.fsx(99,1): error FS0039: The value or constructor 'merge' is not defined

欢迎就代码提出任何建议。感谢您的帮助！

Answer 1

q :: merge q' p :: p'理解为(q :: (merge q' p)) :: p'

这意味着 p 类型必须既是 'a（某些东西）又是 'a list（这些东西的列表）

你真正想要的是q :: merge q' (p :: p')
或者看到 p :: p' 是 b

你可以重写它q :: merge q' b

在 F# 中合并有序列表，期待一个 'a 但给定一个 'a -> a' 列表

Merging ordered lists in F#, Expecting a 'a but given a 'a -> a' list

mergesort

f#

types

list

type-mismatch