是否可以仅使用lambda表达式实现堆栈？

Question

这可能不是一个非常实际的问题,我只是好奇我是否可以实现只有lambda表达式的堆栈.

堆栈支持3个操作:top,pop和push,因此,我首先定义堆栈是一个3元组:

data Stack a = Stack a (a -> Stack a) (Stack a)
             | Empty

这里Empty代表空堆,所以我们至少有一个居民开始.

根据这个定义,除了push操作之外,eveything看起来很好:

import Control.Monad.State
import Control.Monad.Writer
import Data.Maybe

data Stack a = Stack a (a -> Stack a) (Stack a)
             | Empty

safePop :: Stack a -> Maybe (Stack a)
safePop Empty = Nothing
safePop (Stack _ _ s) = Just s

safeTop :: Stack a -> Maybe a
safeTop Empty = Nothing
safeTop (Stack x _ _) = Just x

push :: a -> Stack a -> Stack a
push x s = _

stackManip :: StateT (Stack Int) (Writer [Int]) ()
stackManip = do
    let doPush x = modify (push x)
        doPop    = do
            x <- gets safeTop
            lift . tell . maybeToList $ x
            modify (fromJust . safePop)
            return x
    doPush 1
    void doPop
    doPush 2
    doPush 3
    void doPop
    void doPop

main :: IO ()
main = print (execWriter (execStateT stackManip Empty))

因此,当我完成代码时,我应该能够运行它并获得类似的东西 [1,3,2]

但是,我发现自己扩展了push无限的定义:

push 应该构造一个新的堆栈,第一个元素是刚推入堆栈的项目,第三个元素是当前堆栈:

push :: a -> Stack a -> Stack a
push x s = Stack x _ s

为了填补空洞,我们需要创建堆栈,所以我需要一个let-expression:

push :: a -> Stack a -> Stack a
push x s = let s1 = Stack x (\x1 -> Stack x1 _ s1) s
           in s1

要填补新洞,我需要另一个let-expression:

push :: a -> Stack a -> Stack a
push x s = let s1 = Stack x (\x1 ->
                             let s2 = Stack x1 _ s1
                             in s2) s
           in s1

所以你可以看到我的push定义中总有一个漏洞,但是我扩展了它.

我有点理解背后的魔法Data.Function.fix并猜测一些类似的魔法可以在这里应用,但无法弄明白.

我在想

• 这可能吗？
• 如果答案是肯定的,它背后的魔力是什么？

Answer 1

您可以使用具有Church编码的函数类型完全实现它:

{-# LANGUAGE Rank2Types #-}

newtype Stack a = Stack (forall r. (a -> Stack a -> r) -> r -> r)

cons :: a -> Stack a -> Stack a
cons x (Stack f) = Stack (\g nil -> _)

peek :: Stack a -> Maybe a
peek (Stack f) = f (\x _ -> Just x) Nothing

这表示a Stack是一个函数,它接受一个函数,该函数将顶部元素和堆栈的其余部分作为其参数.该Stack函数的第二个参数是如果堆栈为空时使用的缺省值.我实现了这个peek功能,但是我离开cons了,剩下的就是练习(让我知道你是否需要更多帮助.另外,你留下我放入的下划线cons,GHC将告诉你它预期的类型并列出一些可能相关的绑定).

rank-2类型表示,给定a Stack a,我们可以给它一个返回任何类型值的函数,不受a类型变量的约束.这很方便,因为我们可能不想使用相同的类型.考虑一堆列表,我们想要使用函数Stack来获取顶部元素的长度.更重要的是,它表示像一个函数cons无法以任何方式操纵结果.它必须返回r它从函数中获取的类型值(如果堆栈为空,则返回默认值),不变.

另一个好的练习是实现toList :: Stack a -> [a]并fromList :: [a] -> Stack a表明这两个函数形成同构(意味着它们彼此相反).

事实上,据我所知,所有Haskell数据类型都有一个表示为Church编码.您可以在此Stack类型中看到三种组合类型(总和类型,产品类型和"类型递归")的基本方法.