余再帰あれこれ
corecursion.hs � �? p�~ {--- 余再帰とその利用例 ---} {- 末尾再帰と再帰と余再帰 - - 参考: http://d.hatena.ne.jp/kazu-yamamoto/20091122/1258899591 - - 末尾再帰 : 引数に結果を蓄積し、自身へgotoして処理の流れが戻ってこないようにする。正格なデータを処理する時に用いるとスタックやヒープの節約になる。 - foldl f a [] = a - foldl f a (x:xs) = foldl f (f a x) xs - - 再帰 : 何でもいいから関数内で自分を呼び出してれば再帰。スタックもヒープも消費する。 - quicksort [] = [] - quicksort (x:xs) = quicksort [ l | l <- xs, l <= x ] ++ [x] ++ qui
モナディックなループ - maoeのブログ
しょーもないイディオムの話。モナディックなループを書くとき、だいたい3つくらい宗派があるように思う。 {-# LANGUAGE ViewPatterns #-} module Loop where import Control.Monad (when) import Data.Function (fix) import System.Environment (getArgs) f :: IO () f = do (read -> n):_ <- getArgs flip fix (0 :: Int) $ \loop i -> when (i < n) $ do print i loop $ i + 1 g :: IO () g = do (read -> n):_ <- getArgs let loop i = when (i < n) $ do print i loop $ i + 1
Haskell コード片鑑賞：「再帰」編 - Qiita
今回（前回があったわけではない．もちろん次回以降も未定^^）は再帰があらわれるプログラム断片を鑑賞しましょう． 再帰関数 Haskell使いにとっては再帰は空気のようなものです． 特に意識することなく使います． さらに，多くの再帰パターンは高階関数として抽象化され標準ライブラリで提供されていますので，定義の再帰構造がほとんどコードに現れません． そのおかげで，再帰を愛でる機会がめっきり少くなくなってきています． しかしこれはいかにも残念なことです． 小難しい理屈は最初からやめにして，鑑賞にひたることにしましょう． factorial （階乗） 再帰関数といえば，階乗を計算する関数factorialですよね． 鑑賞のポイント 再帰関数を考えるときの基本: 「現在のステップ」を「一歩手前のステップ」を使って定義する． n+1 パターン: 自然数を分解するパターンで，一般にはn+kパターンという
右も左も分かる再帰 - あどけない話
「函数プログラミングの集い」のチュートリアル資料を作成するためのメモ。リストに対する再帰を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
不動点の話 - あどけない話
不動点コンビネータを使うと、どうして無名関数で再帰ができるのかを考えてみる。 名前を取り去る 以下の階乗を計算する関数 fact を考える。 fact 0 = 1 fact n = n * fact (n - 1) これは、以下のように一つの式に変形できる。 fact n = if n == 0 then 1 else n * fact (n - 1) さらに、ラムダ式に変形できる。 fact = \n -> if n == 0 then 1 else n * fact (n - 1) ここで、fact という名前は使えないので、関数を引数に取るように変更してみる。 fact = (\g n -> if n == 0 then 1 else n * g (n - 1)) fact (※1) 不動点登場 ※1 の無名関数を h で表すとする。 fact = h fact (※2) ここで、x
再帰のパターン - maoeのブログ
Fun of Programming (Cornerstones of Computing)の3章「Origami programming」の冒頭にはこんな事が書かれている。 One style of functional programming is based purely on recursive equations. Such equations are easy to explain, and adequate for any computational purpose, but hard tu use well as programs get bigger and more complicated. In a sense, recursive equations are the 'assembly language' of functional programming, and
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Foldable.mapM_, Maybe, and recursive functions - School of Haskell | School of Haskell
recursion-drill/README.md at main · kazu-yamamoto/recursion-drill