2

我正在尝试解决 F# 中 99 个 Haskell 问题的任务。任务 #7 看起来很简单，并且可以在很多地方找到解决方案。除了我通过谷歌搜索尝试并找到的前几个解决方案（例如https://github.com/paks/99-FSharp-Problems/blob/master/P01to10/Solutions.fs）是错误的。

我的例子很简单。我正在尝试构建非常深的嵌套结构并将其折叠

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 风格重写解决方案，但是我做错了什么或寻找不正确的方向 - 我尝试过的一切都不起作用。

有什么建议吗？

ps Haskell 解决方案，至少在具有 50000 个嵌套级别的嵌套结构上工作缓慢，但没有堆栈溢出。

4

2 回答 2

3

这是使用您的测试不会溢出的 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-04T22:19:20.550 回答
1

免责声明 - 我不是一个深度 F# 程序员，这不会是惯用的。如果您的堆栈溢出，则意味着您没有尾递归解决方案。这也意味着您选择将堆栈内存用于状态。传统上，您希望将堆内存换成堆栈内存，因为堆内存的供应量相对较大。所以诀窍是对堆栈建模。

我将定义一个作为堆栈的虚拟机。每个堆栈元素将是一个状态块，用于遍历一个列表，该列表将包括列表和一个程序计数器，该计数器是要检查的当前元素，并且将是 a 的元组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 附加到列表中。如果它不是一个元素，我会递归，通过使用 NestedList 推送一个新堆栈，然后是当前堆栈元素，PC 提前 1 和其他所有内容。

于 2013-11-05T16:45:40.137 回答