参考Haskell列表中的上一个术语

Question

我希望能够在Haskell中做些什么,但是如果可能的话,这一点并不明显.我是一个新手(例如,我还不了解monad),所以也许有一些先进的方法.

假设我已经将某个类型的函数f定义为自身.我希望能够定义一个概念"prev",它代表列表中的前一个元素(给定类型的元素).所以我想像[x,y,f prev]这样的意思是[x,y,fy].我不介意定义是否涉及用自然数字压缩列表,只要我最后编写的内容可以隐藏构造方法.

这可能是不可能的一个原因是,如果可能的话,那么人们也应该能够定义"下一个"的概念,并且人们不希望能够写出[f next,g prev].如果不可能,还有下一个最佳选择吗？

Answer 1

我不认为有一种方法可以引入一个新的关键字prev来获得您描述的确切语法,至少缺少一些对于这种情况可能是重要的技术,例如隐式参数或模板Haskell.

但是,您可以使用称为绑定递归结的技术来执行此操作:

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.