在 Elm 中使用 Stack ADT 反转字符串

Question

import Html exposing (..)
import String

type alias Stack = List String


push : String -> Stack -> Stack
push tok stack = 
 (tok :: stack)


pop : Stack -> (Maybe String, Maybe Stack)
pop stack = 
 let 
   top = List.head stack 
 in 
 (top, List.tail stack)


reverseString: String -> String
reverseString incoming = 
 let 
   stringStack = incoming 
    |> String.split "" 
    |> List.foldl push [] 
 in 
   -- How to use pop() here?
   List.foldr String.append "" stringStack


main : Html 
main = 
 "Hello World!"
 |> reverseString
 |> toString 
 |> text

我正在尝试使用 push() 和 pop() 自己 reverse 的字符串。我可以合并 push，但无法在函数 reverseString 中使用 pop。我在这里做错了什么？

Answer 1

Elm在语言层面没有迭代，所以你需要使用支持迭代和映射的数据结构。在这种情况下，我认为惰性列表可能是最好的，因为您不会通过递归破坏堆栈。

在这种情况下，stackIterator 从堆栈中生成一个惰性字符串列表。为了获得我们想要的值的惰性序列，我们需要一个函数，我们可以重复应用于它自己的结果，并且由于 pop returns 一个 head, stack 的元组，该函数是 ((mhd, tl) -> 弹出 tl)。接下来的部分作为管道运行，首先拉出元组的左侧部分，第二部分承诺如果返回的堆栈顶部为 Nothing 则终止列表，第三部分通过 [=12] 将 Maybes 的列表转换为字符串=].

只需替换 LL.foldr 和惰性列表，您就可以在涉及弹出函数的堆栈上进行适当的非递归迭代。

几个样式注释：

您的堆栈确实希望 String 成为类型变量。
作为样式选择，您应该更喜欢模式匹配而不是可能返回列表中的函数。
如果 pop returns 堆栈而不是 maybe 堆栈，它会使代码更清晰，因为它可以通过 maybe top 结果发出空堆栈信号。

我自己的榆木风格并不完美。可能有一种不需要显式 lambda 绑定的 snd 和 pop 的聪明方法。

import Html exposing (..)
import String
import Lazy.List as LL exposing (LazyList)

type alias Stack = List String


push : String -> Stack -> Stack
push tok stack = 
 (tok :: stack)


pop : Stack -> (Maybe String, Stack)
pop stack = 
 case stack of
   hd :: tl -> (Just hd, tl)
   _ -> (Nothing, [])

stackIterator : Stack -> LazyList String
stackIterator stack =
 LL.iterate (\(mhd, tl) -> pop tl) (pop stack)
  |> LL.map fst
  |> LL.takeWhile (\a -> a /= Nothing)
  |> LL.map (Maybe.withDefault "") -- Default just for theoretical completeness

reverseString: String -> String
reverseString incoming = 
 let 
  stringStack = incoming 
   |> String.split "" 
   |> List.foldl push [] 
 in 
   LL.foldr String.append "" (stackIterator stringStack)


main : Html 
main = 
 "Hello World!"
 |> reverseString
 |> toString 
 |> text

Answer 2

您正在尝试 List.foldr 使用您的 Stack ADT，但那是作弊；如果 Stack 真的是一个 ADT，我们就不能利用它是一个列表！

List.foldr 与 Stack ADT 的匹配也很差，因为它将其函数参数从处理空列表中解放出来，而 pop 函数迫使我们处理非空和非空列表的情况空堆栈。

如果我们想要 Stack ADT，我们将不得不手动递归堆栈，而不使用 List.foldr。首先，简化 pop 函数以更简洁地表示 "empty stack" 和 "non-empty stack" 的两种情况会很方便：

pop : Stack -> Maybe (String, Stack)
pop stack = 
  case stack of 
    [] -> Nothing
    x :: xs -> Just (x, xs)

然后我们可以制定reverseString

reverseString : String -> String
reverseString string = 
  let
    loop stack = 
      case pop stack of 
        Nothing -> ""
        Just (symbol, stack') -> symbol ++ loop stack'
  in
    String.split "" string   -- Split the string into a list
    |> List.foldl push []    -- Push each letter on the stack
    |> loop                  -- Pop each letter off the stack

直接使用列表可能更容易。然后 Cons (::) 是 push 并且 List.foldl 是通过弹出直到为空来减少堆栈的函数。

reverseString2 : String -> String
reverseString2 = 
  String.split ""        -- "String -> Stack" (implicitly pushes)
  >> List.foldl (::) []  -- "Stack -> List" (reduces the stack)
  >> String.join ""      -- "List -> String" (nothing to do with stacks)

Answer 3

FWIW，我修改了 Rundberget's version 以将字符串用作堆栈。虽然它不像其他解决方案那样通用，但它不使用 List.foldr 或 List.foldl，并且最终变得更短。

module SStack where

import String

type alias SStack = String

empty : SStack
empty =
  ""


push : String -> SStack -> SStack
push tok stacks = 
  tok ++ stacks


pop : SStack -> Maybe (Char, SStack)
pop stacks = 
  String.uncons stacks


reverse : SStack -> SStack
reverse stack =
  case (pop stack) of 
    Nothing ->
      empty
    Just(x, r) -> 
      push  (reverse r) (String.fromChar x)

这是驱动模块：

import SStack as Stack exposing (..)
import Html exposing (..)

reverseString : String -> String
reverseString str =
  Stack.reverse str 


main : Html.Html
main =
  reverseString "Hello World !" 
    |> Html.text

在 Elm 中使用 Stack ADT 反转字符串

Reversing a string using a Stack ADT in Elm

stack

reverse

elm