のOCaml - Lazy.force

Question

はで私のmap関数です：

type 'a stream = Cons of 'a * 'a stream Lazy.t 

let rec ones = Cons(1, lazy(ones));; 

let rec map (f:'a -> 'b) (s:'a stream) : 'b stream = 
    match s with 
    |Cons(h,t) -> Cons(f h, lazy (map f (Lazy.force t)));; 
;; 

正しいですか？ Lazyはそれが既にそれをメモに記入されるようにするだろうか？

Answer 1

はい、正しいです。

ただし、無限のデータ構造（ここではonesなど）の代わりに規則的/周期的に適用すると、計算の共有はありません。 map succ onesのN番目の最初の要素を強制的に適用するとN回succが適用されます。 （実際には、このような規則性/サイクルの形を検出し、それらを終了させる厳密なマッピングを可能にする言語に関する研究がいくつかあります。CoCamlプロジェクトなどを参照してください）

Answer 2

ocaml Lazyタイプにはいくつかの魔法があります。私は、自分で実装するときに怠惰を理解する方が簡単だと思います。構文的には便利ではありませんが、簡単です。トリックは、ここでそれがいつ、どのようにメモ化がLazy'.force中に起こる明らかだ計算

をmemoizeために閉鎖に

利用refの細胞を使用して

• 遅延評価されています。

  module Lazy' : sig 
      type 'a t 
      val delay: (unit -> 'a) -> 'a t 
      val force: 'a t -> 'a 
  end = struct 
      type 'a susp = 
      | NotYet of (unit -> 'a) 
      | Done of 'a 
  
      type 'a t = 'a susp ref 
  
      let delay f = ref (NotYet f) 
  
      let force f = 
      match !f with 
      | Done x -> x 
      | NotYet f' -> 
       let a = f'() in 
       f := Done a; 
       a 
  end 
  

  タイプ 'a stream = Con' 'a *'ストリームLazy'.t ;;

  は ）（ ' ものでもの= はRECものを聞かせ（）=短所（1、Lazy'.delayのもの'）させ;;

  fs = matchsを と一致させる| Cons（h、t） - > Cons（f h、Lazy'delay（fun（） - > map f（Lazy'.force t））） ;;