2026-11-05
SplitAlt.hs
splitAlt :: [a] -> ([a], [a])
リストの1番目、3番目、5番目、…の要素を並べたリストと、2番目、4番目、…の要素を並べたリストを組にして返す splitAlt を書いてください。無限リストを渡しても、組のどちらかの先頭から有限個を取り出せば値が得られるようにします。空リストなら ([], []) を返します。
入力例 1
splitAlt [1, 2, 3, 4, 5]
出力例 1
([1,3,5],[2,4])
入力例 2
take 3 (snd (splitAlt [1 ..]))
出力例 2
[2,4,6]
入力例 3
splitAlt "a"
出力例 3
("a","")
Reference
Reference
splitAlt :: [a] -> ([a], [a])
splitAlt = foldr (\x ~(odds, evens) -> (x : evens, odds)) ([], [])
後ろのリストを分けた組 (odds, evens) があれば、先頭に x を足した全体の組は (x : evens, odds) です。x が新しい1番目になり、それまでの1番目、3番目、…は2番目、4番目、…にずれるので、組の左右が入れ替わります。foldr でこれを右から積み上げ、空リストには ([], []) を対応させます。これは参考実装で、唯一の正解ではありません。
~ を外して \x (odds, evens) -> … と書いても、有限のリストでは同じ結果になります。ただし、ラムダの引数のパターンは、本体を評価する前に照合されます。後ろを分けた結果が組の形かを確かめるには、そのさらに後ろを分け終える必要があります。無限リストではこの確認が終わらないので、入力例2は値を返しません。~(odds, evens) は照合を、odds か evens が使われるまで遅らせます。foldr は再帰の結果を待たずに外側の組 (x : evens, odds) を返せるので、snd と take 3 は必要な分だけ後ろをたどって止まります。where で (odds, evens) = splitAlt xs と束縛する再帰で書いても、同じように無限リストを扱えます。