機能：整数のリストを作成します1..n

StackOverflow https://stackoverflow.com/questions/828765

質問

これは宿題ではありません。私は自分で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;

何かが原因で、再帰で使用される未終了リストを作成するヘルパー関数が必要だと思われますが、困惑しています。

役に立ちましたか？

解決

基本ライブラリの使用

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]

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

他のヒント

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

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

fun list n =
  let
    fun f 1 m = m::nil
    |   f n m = m::f (n-1) (m+1)
  in
    f n 1
  end;

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

fun list n =
  let
    fun aux i acc = 
      if i > 0
      then aux (i-1) (i::acc)
      else acc
  in
    aux n nil
  end;

このようなリストの問題では、より一般的な問題を解決する方が簡単な場合がよくあります。

  

n <！> lt; = i <！> lt; = m などの整数 i を含むリストを順番に作成するにはどうすればよいですか

ソリューションにはベースケースと誘導ステップがあります：

  • If n <！> gt; m 、リストは空です。

  • n <！> lt; = m の場合、解決策は n に続いて問題の解決策 n + 1 < ！> lt; = i <！> lt; = m 。

このビューは、明確で簡潔なMLコード（テスト済み）にすぐにつながります：

fun range n m = if n > m then [] else n :: range (n+1) m
fun list n = range 1 n

(define (iota n)
  (let f ((i n)(a '())
    (if (zero? i)
        (reverse a)
        (f (- i 1) (cons i a)))))
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top