3

これは宿題ではありません。Standard ML を独学で学んでいます。私はSchemeも少し知っているので、この質問はどちらの言語でも答えられるはずです.

私の自主的な課題は、1 から n までの整数のリストを作成する関数を作成することです。たとえば、list(7) は [1,2,3,4,5,6,7] を返す必要があります。O(n) ソリューションが理想的です。

リストを逆に (すなわち [n,n-1,..,1]) 線形時間で構築するのは簡単です:

fun list 1 = 1::nil
|   list n = n::list(n-1);

追加操作は線形であるため、今後リストを作成しようとすると O(n^2) になります。

fun list 1 = 1::nil
|   list n = list(n-1) @ n::nil;

私の次の試みは、nil から始めて n を先頭に付け、逆方向に 1 に再帰することで、最後から先頭 (右から左) へのリストを作成することでした。しかし、それはまったく機能しませんでした。

fun list n = (if n = 1
              then 1
              else list(n-1) :: n) :: nil;

再帰で使用する終了していないリストを作成するヘルパー関数が必要だと思うのですが、困惑しています。

4

6 に答える 6

4

基底ライブラリを使用して、

fun list n = List.tabulate (n, fn x => x + 1)

単純なアキュムレータで、

val list =
    let fun list' k 0 = k
          | list' k n = list' (n::k) (n-1)
    in list' nil end

これにより、末尾から始まるリストが作成されます。値下げを考えれば、

   list 5
=> list' nil 5
=> list' (5::nil) 4
=> list' (4::5::nil) 3
=> list' (3::4::5::nil) 2
=> list' (2::3::4::5::nil) 1
=> list' (1::2::3::4::5::nil) 0
=> [1, 2, 3, 4, 5]

あるいは、

再帰で使用する終了していないリストを作成するヘルパー関数が必要だと思うのですが、困惑しています。

終端されていないリストの表現は、リストを受け取ってリストを返す関数です。たとえば、 を表す10::_には、 を使用できますfn x => 10::x。

fun list n =
    let fun list' m k = if m > n then k nil else
                        list' (m+1) (fn x => k (m::x))
    in list' 1 (fn x => x) end

改めて削減を考えると、

   list 5
=> list' 1 (fn x => x)
=> list' 2 (fn x => (fn x => x) (1::x))
=> list' 3 (fn x => (fn x => (fn x => x) (1::x)) (2::x))
=> list' 4 (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x))
=> list' 5 (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x))
=> list' 6 (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x))
=> (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x)) nil
=> (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::nil)
=> (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::5::nil)
=> (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::4::5::nil)
=> (fn x => (fn x => x) (1::x)) (2::3::4::5::nil)
=> (fn x => x) (1::2::3::4::5::nil)
=> [1, 2, 3, 4, 5]

この場合、アキュムレータには通常のデータ構造で十分なようにアルゴリズムを構成できますが、継続をアキュムレータとして使用することは非常に強力で有用な手法であり、見逃すことはできません。

于 2009-05-06T13:52:34.640 に答える
3

解決策は次のとおりです。

fun list n =
  let
    fun f 1 m = m::nil
    |   f n m = m::f (n-1) (m+1)
  in
    f n 1
  end;
于 2009-05-06T09:37:03.600 に答える
3

ヘルパー関数と末尾再帰を有効にするアキュムレータを使用したバージョンを次に示します。

fun list n =
  let
    fun aux i acc = 
      if i > 0
      then aux (i-1) (i::acc)
      else acc
  in
    aux n nil
  end;
于 2009-05-06T12:45:24.893 に答える
3

古典的なアプローチの 1 つは、逆の順序でビルドしてから逆にすることです。これは O(n) の 2 倍であり、もちろん O(n) と同じです。

于 2009-05-06T09:16:44.397 に答える
0 
(define (iota n)
  (let f ((i n)(a '())
    (if (zero? i)
        (reverse a)
        (f (- i 1) (cons i a)))))
于 2009-05-06T12:39:43.740 に答える