gpt4 book ai didi

haskell - 是否可以仅使用 lambda 表达式来实现堆栈?

转载 作者:行者123 更新时间:2023-12-02 17:14:40 26 4
gpt4 key购买 nike

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

堆栈支持 3 种操作:toppoppush,因此我首先将堆栈定义为三元组:

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

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

在这个定义下,除了push操作之外,一切看起来都很好:

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 表达式:

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

为了填补新的漏洞,我需要另一个 let 表达式:

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 背后的魔力,并猜测这里可以应用一些类似的魔力,但无法弄清楚。

我想知道

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

最佳答案

您可以完全使用具有 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

这表示 Stack是一个函数,它采用一个函数,该函数将顶部元素和堆栈的其余部分作为其参数。 Stack函数的第二个参数是默认值,如果堆栈为空,则使用该默认值。我实现了peek功能,但我离开了cons其余的作为练习(如果您需要更多帮助,请告诉我。此外,您保留我在 cons 中输入的下划线,GHC 会告诉您它需要什么类型并列出一些可能相关的绑定(bind))。

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

另一个好的练习是实现 toList :: Stack a -> [a]fromList :: [a] -> Stack a并证明这两个函数形成同构(意味着它们互为逆)。

事实上,据我所知,所有 Haskell 数据类型都有 Church 编码的表示形式。您可以在此 Stack 中看到组合类型(求和类型、乘积类型和“类型递归”)的三种基本方法。类型。

关于haskell - 是否可以仅使用 lambda 表达式来实现堆栈?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26601561/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com