haskell - 引用 Haskell 列表中的上一个术语

Question

有些事情我希望能够在 Haskell 中完成，但是否可行尚不明确。我是新手(例如，我还不了解 monad)，所以也许有一些高级的方法可以做到这一点。

假设我定义了一个从某种类型到自身的函数 f。我希望能够定义一个概念“prev”，它代表列表中的前一个元素(给定类型的元素)。所以我想 [x, y, f prev] 表示 [x, y, f y]。我不介意定义是否涉及用自然数压缩列表，只要我最后写的东西可以隐藏构造方法即可。

这可能是不可能的一个原因是，如果可能的话，那么人们也应该能够定义“下一个”的概念，而不希望能够写成 [f next, g prev] .如果不可能，是否有下一个最佳选择？

Answer 1

我不认为有一种方法可以引入新的关键字 prev 来获得您描述的确切语法，至少缺少一些对于这种情况来说会显着矫枉过正的技术，比如隐式参数或模板 Haskell。

但是您可以使用一种称为 tying the recursive knot 的技术来做到这一点:

type PrevList a = [a -> a]

instantiatePrevList :: PrevList a -> [a]
instantiatePrevList prevList =
    let result =
           zipWith (\f prev -> f prev)
                   prevList
                   (error "Initial element has no previous element":result)
    in result

xs = instantiatePrevList [\_ -> 5, \_ -> 3, \prev -> prev + 1]

这个想法是根据函数 来定义您的列表，这些函数总是传递先前的值——上面的PrevList 类型。如果特定元素不需要它，您可以选择忽略它。

然后我们需要一个函数将它们放在一起，这就是 instantiatePrevList 所做的。

请注意，列表 result 是根据自身定义的，这就是“打结”的用武之地 - 它依赖于 Haskell 的惰性来工作。

惰性的另一种使用方式是针对第一个元素，它没有前一个元素。只要您不尝试在列表的第一个元素中使用之前的值，就不会发生错误。

正如您猜测的那样，同样的技术也可以用于定义 next - 只要您不编写实际上依赖于自身的东西，它仍然可以正常工作-终止方式。

编辑:

实际上，带有隐式参数的解决方案并不太复杂，它确实有助于编写列表的更好语法:

{-# LANGUAGE ImplicitParams, ImpredicativeTypes, ScopedTypeVariables #-}

type PrevList a = [(?prev :: a) => a]

instantiatePrevList :: PrevList a -> [a]
instantiatePrevList prevList =
    let result =
           zipWith (\(elem :: ((?prev :: a) => a)) prev ->
                             let ?prev = prev in elem)
                   prevList
                   (error "Initial element has no previous element":result)
    in result

xs = instantiatePrevList [5, 3, ?prev + 1]

尽管如此，您确实必须小心处理它们，如果您尝试嵌套它们，您可能会得到令人困惑的结果 - 例如通过在另一个 PrevList 中包含一个 PrevList。