右も左も分かる再帰 - あどけない話「函数プログラミングの集い」のチュートリアル資料を作成するためのメモ。リストに対する再帰を2つに分類することで理解する。 再帰 関数プログラミングでは、繰り返しを再帰で実現する。入力がリストである関数を実装するとする。この種の関数は、出力の種類により以下の2つに分類できる。 同じ順番のリストを作る 数値などを作る。あるいは逆順のリストを作る。 リストからリストを作る再帰 例として、(++)、concat、map、filter の利用例と実装を示す。 (++) (++) は連結(append)関数。 [1,2] ++ [3,4,5] → [1,2,3,4,5] 実装はこう。 (++) :: [a] -> [a] -> [a] (++) [] ys = ys (++) (x:xs) ys = x : (xs ++ ys) concat concat は、リストのリストをリストに平坦化する。 c
