扭轉榆樹

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