在Elm中使用堆栈ADT反转字符串

lifebalance 发表于 Dev

生活平衡

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

我自己尝试reverse使用push()和字符串pop()。我可以合并push，但不能pop在功能内使用reverseString。我在这里做错了什么？

索伦·德布瓦（SørenDebois）

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

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

如果要使用Stack ADT，则必须手动进行整个堆栈的递归，而无需使用List.foldr。首先，方便地简化pop功能以更简洁地表示“空堆栈”和“非空堆栈”两种情况：

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)

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。