99 Haskell問題。 F＃中的＃7 - stackoverflowexception

我試圖從F＃中的99個Haskell問題中解決任務。任務＃7看起來非常簡單，解決方案可以在很多地方找到。除了我試過並通過Google搜索發現的前幾個解決方案（例如https://github.com/paks/99-FSharp-Problems/blob/master/P01to10/Solutions.fs）是錯誤的這一事實。99 Haskell問題。 F＃中的＃7 - stackoverflowexception

我的例子很簡單。我試圖建立極深嵌套結構，並把它摺疊

type NestedList<'a> = 
| Elem of 'a 
| NestedList of NestedList<'a> list 

let flatten list = 
    // 
    (* StackOverflowException 
    | Elem(a) as i -> [a]      
    | NestedList(nest) -> nest |> Seq.map myFlatten |> List.concat 
    *) 
    // Both are failed with stackoverflowexception too https://github.com/paks/99-FSharp-Problems/blob/master/P01to10/Solutions.fs 

let insideGen count = 
    let rec insideGen' count agg = 
     match count with 
     | 0 -> agg 
     | _ -> 
      insideGen' (count-1) (NestedList([Elem(count); agg])) 
    insideGen' count (Elem(-1)) 

let z = insideGen 50000 
let res = flatten z

我試圖重寫CPS風格的解決方案，但eiter我做錯事或考慮不正確的方向 - 一切，我」已經嘗試不起作用。

任何建議？

p.s. Haskell解決方案，至少在嵌套級別爲50000的嵌套結構上運行緩慢，但沒有堆棧溢出。

來源

2013-11-04 galkk

你用什麼選項來編譯？ –

我試圖在VS 2013發佈模式下運行（Ctrl + F5），並打開「生成尾呼叫」複選框 – galkk

這是一個CPS版本，不會使用您的測試溢出。

let flatten lst = 
    let rec loop k = function 
    | [] -> k [] 
    | (Elem x)::tl -> loop (fun ys -> k (x::ys)) tl 
    | (NestedList xs)::tl -> loop (fun ys -> loop (fun zs -> k (zs @ ys)) xs) tl 
    loop id [lst]

編輯

一個更可讀的方式來寫，這將是：

let flatten lst = 
    let results = ResizeArray() 
    let rec loop = function 
    | [] ->() 
    | h::tl -> 
     match h with 
     | Elem x -> results.Add(x) 
     | NestedList xs -> loop xs 
     loop tl 
    loop [lst] 
    List.ofSeq results

來源

2013-11-04 22:19:20 Daniel

我正在閱讀本文時，我的大腦正在融化，但謝謝。將嘗試理解。 – galkk

這也是我的第一個傾向，但我希望有一個不涉及'@'的乾淨解決方案。編輯：我喜歡編輯。 ; - ] – ildjarn

@galkk：我不認爲我會這樣寫在生產代碼中。它運行良好，但它像Perl腳本一樣可讀。我用更美味的版本更新了我的答案。 – Daniel

免責聲明 - 我不是一個深刻的F＃程序員，這不會是習慣。如果您的堆棧溢出，這意味着您沒有尾部遞歸解決方案。這也意味着你正在選擇使用堆棧內存狀態。傳統上，由於堆內存的供應量相對較大，因此您希望爲堆棧內存交換堆內存。所以訣竅是建立一個堆棧模型。

我打算定義一個作爲堆棧的虛擬機。每個堆棧元素將是一個狀態塊，用於遍歷列表，該列表將包含列表和程序計數器，該計數器是當前要檢查的元素，並且將是一個NestedList<'a> list * int的元組。該列表是當前正在遍歷的列表。 int是列表中的當前位置。

type NestedList<'a> = 
    | Elem of 'a 
    | Nested of NestedList<'a> list 

let flatten l = 
    let rec listMachine instructions result = 
     match instructions with 
     | [] -> result 
     | (currList, currPC) :: tail -> 
      if currPC >= List.length currList then listMachine tail result 
      else 
       match List.nth currList currPC with 
       | Elem(a) -> listMachine ((currList, currPC + 1) :: tail) (result @ [ a ]) 
       | Nested(l) -> listMachine ((l, 0) :: (currList, currPC + 1) :: instructions.Tail) result 
    match l with 
    | Elem(a) -> [ a ] 
    | Nested(ll) -> listMachine [ (ll, 0) ] []

我做了什麼？我寫了一個尾部遞歸函數，運行「Little Lisper」樣式代碼 - 如果我的指令列表爲空，則返回我的累計結果。如果不是，請在堆棧頂部進行操作。我將一個便利變量綁定到頂端，如果PC在最後，我會在當前結果的堆棧尾部彈出（pop）。否則，我查看列表中的當前元素。如果這是一個Elem，我會緩慢推進PC並將Elem添加到列表中。如果它不是elem，我會推薦一個新的堆棧，其中包含NestedList，隨後是當前堆棧elem，並且PC先進1，等等。

來源

2013-11-05 16:45:40 plinth

99 Haskell問題。 F＃中的＃7 - stackoverflowexception

回答

相關問題