Maybe 的 Haskell 递归实现

Question

我是 Haskell 新手，我尝试实现一个堆栈。

data Stack a = Stack [a] deriving Show

emptyStack :: Stack a
emptyStack = Stack []

push :: a -> Stack a -> Stack a
push element (Stack s) = Stack (element:s)

isEmpty :: Stack a -> Bool
isEmpty (Stack s) = null s

pop :: Stack a -> Maybe [a]
pop (Stack []) = Nothing
pop (Stack (x:xs)) = Just xs

main = do
    print (pop (Stack [1..10])) 
    -- Just [2,3,4,5,6,7,8,9,10]
    
    print (push 1 $ push 2 $ push 3 (Stack [1..10]))
    -- Stack [1,2,3,1,2,3,4,5,6,7,8,9,10]
         
    print (pop (Stack [1]))
    -- Just []
    
    print (pop $ pop (Stack [1..2]))
    -- Compile Error

在上面的代码中，我想像 print (pop $ pop (Stack [1..2])) 行那样多次弹出，但由于数据类型，它会导致错误.

实现这个 pop 函数的正确方法是什么，这样我就可以连续调用它并对空堆栈有正确的行为。

此外，我仍然想知道如何在来自命令式语言背景的现实世界应用程序中使用 Haskell。我喜欢它并且想在网络应用程序中使用它。

Answer 1

您的push获取一个堆栈并返回一个堆栈。制作您的pop的第一步这样的工作方式是获取一个堆栈并返回一个堆栈——而不是返回一个列表，这是一种不同的数据类型!

pop :: Stack a -> Maybe (Stack a)
pop (Stack []) = Nothing
pop (Stack (x:xs)) = Just (Stack xs)

当组合多个调用 push 时，您使用$ :

push 1 $ push 2 $ push 3 (Stack [])

($)函数的输出为push并将其提供给另一个对 push 的调用。所以它有一个接受 push 的类型输出并将其传递给push类函数:

($) ::
    -- the type of push foo
    (Stack a -> Stack a) ->
    -- the type of a previous push's output
    Stack a ->
    -- the output type we want from pushing twice
    Stack a

它的实现非常简单:

f $ stack = f stack

还有一个你一开始可能不会想到的小问题:应该 f $ g $ stack意思是(f $ g) $ stack或f $ (g $ stack) ？对于我们正在做的事情，我们想要后者。我们必须告诉编译器这一点，这可以通过固定声明来完成:

infixr 0 $

这表示$的重复应用应该分组到右边。还有infixl当事物应该向左分组时，以及 infix当编译器不应该自动对事物进行分组时。您现在可以忽略该号码。

制作 pop 的第二步像push一样工作所做的就是发明一个函数，其输出为 pop并将其提供给另一个对 pop 的调用。自 pop返回 Maybe (Stack a) ，我们需要让它采取其中之一。由于历史原因，我将选择名称 (=<<) ，但你可以选择任何你更喜欢的名字——也许 $+或表明它是“加强版”的东西 $ 。它应该有什么类型？嗯，应该需要 pop输出并将其输入到 pop 。所以:

(=<<) ::
    -- the type of pop
    (Stack a -> Maybe (Stack a)) ->
    -- the type of previous pop's output
    Maybe (Stack a) ->
    -- the output we want from doing two pops
    Maybe (Stack a)

它的实现比($)要多一些工作。是，但不多:

f =<< x = case x of
    Just stack -> f stack
    Nothing -> Nothing -- what else can you do? there's no stack to feed to f

和以前一样，我们需要一个固定性声明，并且和以前一样，我们需要右关联性。

infixr 1 =<<

现在我们可以将调用链接到 pop :

pop =<< pop =<< pop (Stack [1,2,3])

享受吧!

附注其实$有一个比我在这里展示的更通用的类型:

($) :: (a -> b) -> a -> b

事实证明我们的=<<也有比上面显示的更通用的类型:

(=<<) :: (a -> Maybe b) -> Maybe a -> Maybe b

P.P.S。接下来你需要混合push和pop 。您很快就会发现 $ 可能有很多变体。和=<<您需要写...在下面的每个位置，您可以选择 Maybe或不:

(Maybe? a -> Maybe? b) -> Maybe? a -> Maybe? b

其中许多实际上是由 $ 中的多态性处理的。的现有类型 - 您对 Maybe 做出相同选择的类型/不Maybe在第一和第三位置以及第二和第四位置。您可能会很高兴思考剩下的可能性。都可以写吗？ (不。为什么不呢？)

实际上，大多数人只需四个操作即可完成大部分工作:

($)   :: (a ->       b) ->       a ->       b
(=<<) :: (a -> Maybe b) -> Maybe a -> Maybe b
(<$>) :: (a ->       b) -> Maybe a -> Maybe b
pure  :: a -> Maybe a

(当您想要执行的转换是从函数输入之前删除 Maybe 而不更改其输出类型时，请使用最后一个，它并不完全符合模式。)