扭转榆树

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 

我试图用一个Stack ADT字符串我自己reverse使用push()和pop()字符串。我能够在函数reverseString中合并push，但不能使用pop。我在这里做错了什么？

Answer 1

您正试图List.foldr与堆栈ADT，但是这是欺骗;如果Stack真的是ADT，我们不应该能够利用它的列表！

List.foldr也与Stack 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 (::)被推入，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 2

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

在这种情况下，stackIterator会从堆栈中产生一个懒惰的字符串列表。为了得到我们想要的懒惰的值序列，我们需要一个我们可以重复应用到它自己的结果的函数，并且由于pop返回一个头元组，堆栈，该函数是（（mhd，tl） - > pop tl ）。接下来的部分作为流水线运行，首先拉出元组的左侧部分，第二部分承诺如果返回的堆栈顶部为Nothing，则终止列表;第三，通过Maybe.withDefault将Maybe s的列表变成字符串。

通过用LL.foldr和惰性列表代替，您的堆栈中有一个适当的非递归迭代，涉及您的弹出功能。

一对夫妇的风格调：

• 你的筹码真的想串是一种类型的变量。
• 作为一种风格选择，你应该更喜欢模式匹配函数返回可能在列表上。
• 它使得代码更清晰，如果pop返回堆栈而不是堆栈，因为它可以通过可能的最高结果发信号通知空栈。

• 我自己的榆木风格并不完美。可能有一个巧妙的方法来编写snd和pop，它不需要显式的lambda绑定。

  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 3

FWIW，我修改了Rundberget's version以使用String作为堆栈。虽然它不像其他解决方案那样通用，但它不使用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