功能程序通过类型分析"自己编写"的例子

Question

(背景:我一直在考虑做关于F#和函数式编程的演示.从经验来看,我认为模式匹配和类型推断的'哇'因素不一定足以抵消'帮助!'因素"是我的大括号和分号,我的代码将脱离边缘!".这让我想到真正令人惊叹的因素 - 对我来说 - 这是1)如果它编译,通常这意味着它的工作原理2)您经常可以从类型中推断出实现)

Channel9与Brian Beckman和Erik Meijer 有一段视频,他们提到了实现有时只是"失去"函数的类型签名.我过去也经历过这种情况,但是不能提出一个很好的例子,这个例子很容易呈现给没有任何功能经验的人.

有没有人有一个很好的例子可以分享？(它不必在F#中)

UPDATE

如果有任何帮助,我认为我们需要以不同的方式思考:实际的难题如下:

我有一些给定类型的数据,我想将它转换为另一种类型,我有一组具有给定签名的函数.

这是你必须插在一起的"乐高".

Answer 1

从最简单的功能开始:identity :: 'a -> 'a.你能想到多少个实现？如果你给我一个a,我只能用它做一件事来给你回复a.我给你的回报和a你给我的一样,所以:

let id x = x

配对也一样.fst :: ('a,'b) -> 'a.你有多少种方法可以实现？怎么样snd :: ('a, 'b) -> 'b？每个可能只存在一个实现.

类似地,以列表的头和尾落在右出的fst和snd.如果head :: 'a list -> a和tail :: 'a list -> 'a list,并且a 'a list只是一对('a, 'a list)(或空列表),那么很明显,为了满足类型,您分别返回列表的第一部分和第二部分.

高阶函数的另一个例子:compose :: ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b.只有一个实现,它完全属于类型.你有一个c和两个功能.你能做些什么c？好吧,你可以申请(c -> a).那你可以做些a什么呢？你唯一能做的就是申请(a -> b),瞧,你已经满足了这种类型.

let compose f g x = f (g x)

Answer 2

管

这是第三个例子......

假设我想写一个函数

p : 'a -> ('a -> 'b) -> 'b

也就是说,我将一个类型为a的值作为参数,并将一个带有'a并返回'b的函数作为参数.我的结果应该是'b.好吧,再次,modulo无限循环和异常以及默认初始化,只有一个实现:

let p x f = f x

在您意识到它是管道运算符(|>)之前,'p'可能看起来不太有用.

嗯,我觉得到目前为止这些例子并没有给人留下深刻印象.

Answer 3

地图

还有几个要考虑......

om2 : ('a -> 'b) -> 'a option -> 'b option

唯一有趣的实现是Option.map:

let om f xo =
    match xo with
    | None -> None
    | Some x -> Some(f x)

现在我可以写了

let om (f:'a -> 'b) (xo:'a option) : 'b option =
    None

并且只是忽略两个参数并始终返回None.但这并不有趣.有人向我们传递了所有这些有用的论据,当然我们打算与他们做点什么,对吧？所以上面的第一个实现是唯一的一个(再次模拟其他答案中提到的小事,由于循环,效果等).

同样

lm : ('a -> 'b) -> 'a list -> 'b list

你很难写出除List.map以外的任何东西.你总是可以返回空列表,但是它会忽略这两个参数.你可以写

let lm f xs =
    match xs with
    | [] -> []
    | h::t -> [f h]

但是对于某人传递这整个有用的列表似乎很奇怪,我们忽略了除第一个元素之外的所有内容.如果您认为"意味着"'使用'所有数据,List.map就是明显的实现.(虽然没有什么可以阻止你映射两次或三次并返回一个2x或3x与原始列表一样长的新列表.再一次,有一种感觉/美学,其中有一个'最简单明显'的实现与类型签名匹配并使用传入的数据,这个"显而易见"的实现很有用.当你看到签名时

('a -> 'b) -> 'a list -> 'b list

你只想到'List.map',没有人会考虑所有其他理论上可能的实现,因为其他的在软件工程环境中几乎都是无意义的.)

我不知道这是否有说服力.

Answer 4

底部

好吧，这不是一个超级好的例子，但是“好吧”，也许会有助于实现其他一些想法......

认为

f : unit -> 'a

也就是说，我想编写一个不传递参数的函数，并且它返回任何类型的值。该函数有什么作用？

请注意，我不能只返回“new obj()”，因为类型签名是通用的，例如，我可以使用 f<int> 调用它并返回 int。

放弃？这是最常见的可能性：

let rec f() = f()

这是一个无限循环。它永远不会返回，因此返回类型无关紧要。您可以在多种语言中执行此操作。

在像 Haskell 这样的语言中，“异常”将是由类型系统控制的“效果”，但在 F# 中：

let f() = failwith "kaboom!"

另一个例子。如果我们再次抛出异常，返回类型并不重要。

最后，许多运行时的实现细节允许任何类型的“默认初始化”，例如在 F# 中

let f() = Unchecked.defaultof<'a>

也可以。我认为也许这是 F# 中仅有的三种可能的实现。