ゼロのリストのパッドの終わり

Question

[13,7,8,4]と数字Nのようなリストがあります。そのリストの最後に "N mod ListSize"の数で要素（いくつかのゼロ）を挿入したいとします。 N = 6とし、リストに従って、ListSizeは4です。したがって、6 mod 4 = 2であり、次にこのように2ゼロを挿入する必要があります。[13,7,8,4,0,0]

SMLの関数でこれを行うにはどうすればよいですか？

Answer 1

リストの末尾のパッドは、O（n）の操作です。 origが元のリストで、zeroesが埋め込みゼロである場合、には、origからzeroesのすべての要素が付加されます。

構成上のアプローチは、最初にゼロの数を見つけ、それらのゼロを作成してから追加することです。

fun numberOfZeroes xs n = n mod List.length xs 

fun replicate x 0 = [] 
    | replicate x n = x :: replicate x (n-1) 

fun zeroes xs n = replicate 0 (numberOfZeroes xs n) 

fun pad xs n = xs @ zeroes xs n 

あなたは（別のlength/@とは違って）ゼロが追加されていると同時にxsの長さをカウントすることにより、1つのトラバーサルを救うことができます。組み合わせた機能は次のようになります。大xsのために、それはスタック領域が不足する可能性がありますので

fun pad xs n = 
    let fun pad' (x::xs) count = x :: pad' xs (count + 1) 
      | pad' [] count = replicate 0 (count mod n) 
    in pad' xs 0 end 

この機能は、しかし、末尾再帰的ではありません。 （replicateはどちらでもないが、長さはNのリストのみを生成する）。逆方向にテール再帰的にするには、リストを2回横断する必要があります。また、より複雑でない機能から複雑な機能を構築することは、認知負荷を減少させる。

最後に、問題の説明は非常にうまくいきました。次回同様に問題の明確な説明がある場合は、正しい実装が合格するようにテストを試してみてください。例えば。あなたが説明したテストは、次のとおりでした：

val test1 = pad [13,7,8,4] 6 = [13,7,8,4,0,0] 

すべてのコーナーケースを定義するまで、さらにテストを追加してください。例：

val test2 = pad [13,7,8,4] 4 = ?