我是Haskell的新手,我有以下问题。我有一个函数foo,它必须应用一个函数(由参数给出),直到没有更多的变化。这就是函数的签名
foo :: (a-> a )-> a-> a
我试了一下
foo f x = if ((f x) == x) then x else foo (f (f x))
我明白了
No instance for (Eq a) arising from a use of `=='
我知道 何以 我明白了(a是通用的,所以编译器不知道是否派生出了 Eq
),但不知道如何解决。我在想一种方法,在两种情况下对函数进行划分(当输入派生为 Eq
而当它没有的时候),但我没有找到一个方法来做。所有我找到的解决这个问题的方法都是把函数的签名改成了 Eq a
但我不允许更改签名。
PS:我不关心当参数不导出Eq时函数的作用,因为我不会在这种情况下使用它。
编辑:我做了Willen说的修正。
这种类型的函数不多。忽略那些只会产生错误或无限循环的东西,你有
foo :: (a -> a) -> a -> a
foo f _ = r where r = f r
习惯性的说,我们会用这样的方式来写 Data.Function.fix
:
fix :: (a -> a) -> a
fix f = r where r = f r
foo f _ = fix f
这只是给你 f (f (f (f ...)))
这可能是或可能不是很好的定义,这取决于 f
原来是这样。
bar :: Natural -> (a -> a) -> a -> a
bar 0 _ a = a
bar n f a = f (bar (n - 1) f a)
应用 bar
的自然数产生一个你想要的类型的函数,应用给定次数的参数函数。
就这样了。没有更多的函数了。
{foo} ∪ {bar n | n ∈ N}
是你给定类型的有趣(部分)函数的全部集合。如果你想要更多有趣的函数,你需要更多的约束。
如何 foo
关系到 bar
? 嗯,有一种说法是 foo
是你会得到什么通过应用 bar
到 "无穷大"。我们可以定义扩展的自然数(the 亚历山德罗夫一点压实 的自然数)这样。
data ExtendedNat = N Natural | Inf
但这并不能帮助解释 foo
和 bar
. 一个更自然的方法是使用 懒惰自然数 而不是。
data Nat = Z | S Nat
现在,无穷大被表示为 S (S (S ...))
:
infty :: Nat
infty = fix S
我们可以写
barf :: Nat -> (a -> a) -> a -> a
barf Z _ a = a
barf (S n) f a = f (bar n f a)
现在 foof
是专门
foof = barf infty