0

I'm trying to create a function that returns itself in a tuple of values. Basically the idea is that the caller would get back transformed values, along with a new (curried) version of the function to use further along in the processing.

However, at the moment, I'm stuck trying to come up with a no-op (i.e. do-nothing) version of this function. So the following snippet is obviously fine - this is a no-op which doesn't return itself:

noOp s as xs = (s, as, xs)

But if I change to this:

noOp s as xs = (s, as, xs, noOp)

I get the "infinite type" error:

Occurs check: cannot construct the infinite type:
  t3 = t0 -> t1 -> t2 -> (t0, t1, t2, t3)
In the expression: noop
In the expression: (s, as, xs, noop)
In an equation for `noop': noop s as xs = (s, as, xs, noop)

There's plenty of discussion on SO about handling the infinite type error - but I can't quite figure out how to apply to my problem.

Any advice welcomed...

4

3 回答 3

9

要表达这样的东西，你需要一个递归类型。由于 Haskell 不支持等递归类型，因此您需要使用newtype/ data。

newtype Foo s = Foo { runFoo :: s -> (s, Foo s) }因此，例如，您可以定义，然后编写noOp :: Foo (A,B,C); noOp = Foo (\(a,b,c) -> ((a,b,c), noOp))。

这看起来像一台 Mealy 机器。该包machines 导出类似的类型：newtype Mealy i o = Mealy { runMealy :: i -> (o, Mealy i o) }

于 2013-08-15T09:23:10.297 回答
1

您面临的问题是您有一个无限递归类型！noOp 的类型类似于

noOp :: a -> b -> c -> (a,b,c,a -> b -> c -> (a,b,c,a -> b -> c -> (a,b,c,...))))

如您所见，我们永远无法完全写出 of 的类型，noOp因为它依赖于 的类型noOp。如果我们可以封装noOp我们可以通过名称引用它的类型。

但是，事实上，我们可以做到！

data Foo a b c = Foo (a -> b -> c -> (a,b,c,Foo a b c))

如您所见，递归被捕获是因为我们通过Foo a b c. 现在有必要打包和解包：

runFoo (Foo f) = f

noOp s as xs = Foo (s, as, xs, noOp)

现在，我同意，这似乎有点不方便，但对于一个真正的应用程序，你可能会找到一个比Foo保存你的值更合适的数据结构，可能类似于

data Bar s as xs = Bar s as xs (Bar s as xs)
于 2013-08-15T14:41:43.150 回答
1

只是回答@augustss 想说的话。要走的路是使用递归类型，如

data Foo a = Foo a (a -> Foo a)
noop :: a -> Foo a
noop a = Foo a noop
于 2013-08-15T09:23:11.937 回答