如何創建標準ML中增加尺寸的按需呼叫列表？

Question

我想創建一個列表元素，它們一起表示所有零和零的組合。

實施例：[[]，[0]，[1]，[0,0]，[0,1]，[1,0] ...]

這甚至可能在ML？我似乎無法找到一種方法來改變列表元素的模式，一旦我定義了它。似乎還需要定義二進制模式的變化，這在函數式語言中是不可能的（我從來沒有在函數式​​語言中遇到二進制表示）？

Answer 1

似乎有是兩個不同的問題在這裏手：

1. 我們如何產生這個特殊的無限數據結構？
2. 在ML中，我們如何實現按需呼叫？

---

讓我們首先考慮的第一點。我將在步驟中生成這個特定的數據結構，其中步驟的輸入是長度爲的所有位模式的列表，其中爲。我們可以通過在每個長度爲n的模式上預置0和1來生成長度爲n + 1的所有位模式。在代碼中：

fun generate patterns = 
    let 
    val withZeros = List.map (fn pat => 0 :: pat) patterns 
    val withOnes = List.map (fn pat => 1 :: pat) patterns 
    val nextPatterns = withZeros @ withOnes 
    in 
    current @ generate nextPatterns 
    end 

val allPatterns = generate [[]] 

如果您要在需要調用的語言（如Haskell）中實現此方法，它將在開箱即用的情況下運行良好。但是，如果您在ML中運行此代碼，它將不會終止。這給我們帶來了第二個問題：我們如何在ML中進行按需呼叫？

---

要做到在ML調用 - 需求，我們需要與懸浮工作。直觀地說，暫停是可能還未運行的一部分計算。下面顯示了一個合適的界面和實現。我們可以用delay暫停計算，防止其立即運行。後來，當我們需要暫停計算的結果時，我們可以用force它。這個實現使用引用來記住先前強制掛起的結果，保證任何特定的掛起最多隻會被評估一次。

structure Susp :> 
sig 
    type 'a susp 
    val delay : (unit -> 'a) -> 'a susp 
    val force : 'a susp -> 'a 
end = 
struct 
    type 'a susp = 'a option ref * (unit -> 'a) 
    fun delay f = (ref NONE, f) 
    fun force (r, f) = 
    case !r of 
     SOME x => x 
    | NONE => let val x = f() 
       in (r := SOME x; x) 
       end 
end 

接下來，我們可以在懸浮液，其中所述列表的尾部被延遲來定義一個懶惰列表類型。這使我們能夠創建看似無限的數據結構;例如，fun zeros() = delay (fn _ => Cons (0, zeros()))定義了一個零的無限列表。

structure LazyList :> 
sig 
    datatype 'a t = Nil | Cons of 'a * 'a t susp 

    val singleton : 'a -> 'a t susp 
    val append : 'a t susp * 'a t susp -> 'a t susp 
    val map : ('a -> 'b) -> 'a t susp -> 'b t susp 

    val take : 'a t susp * int -> 'a list 
end = 
struct 

    datatype 'a t = Nil | Cons of 'a * 'a t susp 

    fun singleton x = 
    delay (fn _ => Cons (x, delay (fn _ => Nil))) 

    fun append (xs, ys) = 
    delay (fn _ => 
     case force xs of 
     Nil => force ys 
     | Cons (x, xs') => Cons (x, append (xs', ys))) 

    fun map f xs = 
    delay (fn _ => 
     case force xs of 
     Nil => Nil 
     | Cons (x, xs') => Cons (f x, map f xs')) 

    fun take (xs, n) = 
    case force xs of 
     Nil => [] 
    | Cons (x, xs') => 
     if n = 0 then [] 
     else x :: take (xs', n-1) 
end 

有了這個機器在手，我們可以適應原代碼，使用惰性列表和懸浮在適當的地方：

fun generate patterns = 
    delay (fn _ => 
    let 
     val withZeros = LazyList.map (fn pat => 0 :: pat) patterns 
     val withOnes = LazyList.map (fn pat => 1 :: pat) patterns 
     val nextPatterns = LazyList.append (withZeros, withOnes) 
    in 
     force (LazyList.append (patterns, generate nextPatterns)) 
    end) 

val allPatterns = generate (LazyList.singleton []) 

我們可以強制一塊這份名單與LazyList.take：

- LazyList.take (allPatterns, 10); 
val it = [[],[0],[1],[0,0],[0,1],[1,0],[1,1],[0,0,0],[0,0,1],[0,1,0]] 
    : int list list