list - Haskell リストの左パディング

Question

整数の Haskell リストを右パディングしたい場合は、次のようにすることができます。

rpad m xs = take m $ xs ++ repeat 0

リストの長さを取得する必要はありません。かなり高性能になると思います。

lpad長さなどを数えるコストを負担することなく、左側のリストをパディングしてdefinte できる同様の方法はありますか?

Answer 1

したがって、最初に言う価値があるのは、パフォーマンスの本質についてあまり心配しないことです。このコードは、実行時間の 80% を占めることわざのコードの 20% に収まる可能性は低いです。

そうは言っても、ここでパフォーマンスが本当に重要なのはどこですか? mが小さいか、length xs巨大か無限かが重要です。mつまり、が大きい場合に良好なパフォーマンスが得られるとよいでしょう( のrpad場合のように、リストの最初のk項目のみを処理するとk、いくつかの に対してのみ機能しますk << m) が、もちろん問題の説明そのもので、m上位の結果を表示するために作業を行う可能性があります。(無限リストが提供されている場合は、最初の要素mを返すかどうかを知るためにアイテムを覗く必要があります。)0

その場合、 のtake m xs代わりにゼロパディングが本当に必要ですxs。それが全体のトリックです：

lpad m xs = replicate (m - length ys) 0 ++ ys
    where ys = take m xs

Answer 2

右パディングは、出力リストの最初の要素を生成するために、入力リスト (または) の最初のコンストラクターを調べるだけで済みます。これはストリーミング操作です ( で実行できます)。:[]foldr

左パディングは、出力リストの最初の要素を生成するために、入力リスト全体を調べる必要があります。つまり、最初の要素が であるかどうかは、リストの末尾に依存します (それが で始まらないと仮定します)。これは、ストリーミング方式では実行できません。O(min(m,length)) は、最初の要素についてのみ取得できる最高のものです。00

mまた、入力リストがそれよりも長い場合、パディング関数は -th の後の要素を破棄するので注意してください。これは望ましくない場合があります。要素を追加するだけで削除できないようにパディングが定義されている場合があります。

Answer 3

@ソロモン・ウッコ

なぜlength2 回電話をかけるpadLのですか (他の人も同じです)。どうですか

padL :: a -> Int -> [a] -> [a]
padL p s l
    | length' >= s = l
    | otherwise    = replicate (s - length') p ++ l
      where length' = length l