在SML

Question

平展流我有這樣的數據類型：

datatype 'a stream' = Susp of unit -> 'a stream 
and 'a stream = Empty | Cons of 'a * 'a stream' 

，我想寫它有以下類型扁平化功能。

flatten: ’a stream’ stream’ -> ’a stream’ 

flatten函數將把流作爲輸入流，並通過追加它們來壓扁它。

我如何做到這一點？有任何想法嗎？

謝謝。

編輯：我知道如何做它的列表。這很簡單： fun flatten [] = [] | flat (l::ls) = l @ flatten ls; 幫助我與流請，我不知道如何模式匹配流的流。

Answer 1

讓我們寫它list第一：

fun append(xs, ys) = case xs of 
    [] => ys 
    | (x::xs) => x :: append(xs, ys)    

fun flatten(xss) = case xss of 
    [] => [] 
    | (xs::xss) => append(xs, flatten(xss))    

上面應該是顯而易見的。現在，我們只需要稍微改變它支持stream，通過Susp結束和force在適當的步驟-ing：

fun force(Susp(xs)) = xs()           

fun append(xs, ys) = case force xs of 
    Empty => ys 
    | Cons(x,xs) => Susp(fn() => Cons(x, append(xs, ys))) 

fun flatten(xss) = case force xss of 
    Empty => Susp(fn() => Empty) 
    | Cons(xs,xss) => append(xs, flatten(xss))