2003-06-17 [長年日記]
λ. ドイツ語
藁谷先生は面白いなぁ。
λ. 萩野服部研
SICP 5.1 「レジスタ計算機の設計」
λ. [a1; a2...; an] と[b1; b2...; bn] を受け取って, [(a1, bn); (a2, bn - 1); ...; (an, b1)] を返す関数
水凪さんの日記の4/17に載っていた問題。帰りの電車とバスの中で結構真剣に考えてしまった。気づけば簡単。
長さの等しい二つのリスト[a1; a2...; an]と [b1; b2...; bn]を 受け取って, [(a1, bn); (a2, bn - 1); ...; (an, b1)] を返す関数を書きなさい。 ただし、
- nをあらかじめ知ることはできない
- 与えられた二つのリスト以外のリストを使ってはならない
- 再帰呼び出しは高々(n + 1)回しか行ってはならない
- 全体の計算量はO(n)でなければならない
hoge :: [a] -> [b] -> [(a,b)]<br>hoge as bs = zip as (reverse bs)<br>で、見掛上再帰なし。じゃだめですよねぇ。<br>三つめの条件がよくわからないです。むずかすぃ
これでいいんですかね…<br><br>xzip xs ys = f where (f,s) = xzip' xs ys<br><br>xzip' [] ys = ([], ys)<br>xzip' (x:xs) ys = ((x,y):list, ys')<br> where (list, (y:ys')) = xzip' xs ys
確かに問題が結構曖昧ですよね。<br><br>nobsunさんのは、zipとreverseはそれぞれn回の再帰で実行できるので、<br>条件の解釈にもよるかも知れませんが、3つ目の条件は満たしてると思います。<br>ですが、reverseで一時的なリストを作っているので、<br>2つ目の条件で多分アウトです。(^^;<br><br>あおきさんのは文句なしであってると思います。<br>ちなみに、リンク先の4/25の日記に解答があるのですが、<br>あおきさんの解答の方がスマートですね。
Haskell ワカリマセーン．ruby か scheme で書いてー．
あっ。なるほど。mapAccumR だ。<br>xzip as bs = snd $ xzip' as bs<br>xzip' = flip (mapAccumR f) where f (y:ys) x = (ys,(x,y))<br>ですね。