余再帰あれこれ
corecursion.hs @��1 V 0� . V {--- 余再帰とその利用例 ---} {- 末尾再帰と再帰と余再帰 - - 参考: 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] ++
Total functional programming - Wikipedia
Total functional programming (also known as strong functional programming,[1] to be contrasted with ordinary, or weak functional programming) is a programming paradigm that restricts the range of programs to those that are provably terminating.[2] Termination is guaranteed by the following restrictions: A restricted form of recursion, which operates only upon 'reduced' forms of its arguments, such
モナディックなループ - 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パターンという
Scala @tailrecメモ(Hishidama's Scala @tailrec Memo)
概要 scala.annotation.tailrecアノテーションは、末尾再帰でないメソッドの場合にコンパイルエラーにするアノテーション。 再帰するメソッド（自分自身を呼び出すメソッド）は、呼び出す回数が多くなるとその分スタックフレームを消費してしまう（最悪はOutOfMemoryErrorが発生する）が、 末尾再帰だと効率の良いループに変換してくれる。 tailrecアノテーションを付けておくと、誤って末尾再帰になっていない時にコンパイルエラーになってくれる。 例 @tailrecの使用例。 import scala.annotation.tailrec メソッドが末尾再帰でないとコンパイルエラーになる。 （再帰呼び出し部分が呼び出した結果との演算になっていると、末尾再帰に出来ない） scala> @tailrec | def f(n: Int): Int = { | if (n <=
let が再帰でない理由というかメリット - camlspotter’s blog
そうすると本当に rec の存在意義を疑うしかなくなる。もし何らかの理由で付いてると嬉しいのだとしても、現代的な言語だったらプログラマが怠けられるようにそういうのは排除するべきじゃないでしょうか。納得できそうな理由があったら教えてください。 OCaml の再帰関数 - はいお教えします。再帰で書きたくない時もあるので、デフォルト再帰だと困るからです。ある identifier を、その値を使いつつ再定義する際に必要です: let _ = let verbose = ref false in Arg.parse [ "--verbose"; Arg.Unit (fun () -> verbose := true); "verbose mode"; ... ] (fun s -> ...) "command [options]"; let verbose = !verbose in ... i
OCaml の let と let rec はなぜ別扱いになっているのか、決定版、もしくは OCaml 暦十何年だったか忘れたけど仕事で Haskell を一年使ってみた - camlspotter’s blog
はじめに断っておくが、全部Pros/Consのあるデザインチョイスなので、こうじゃなきゃいけないってことではない。ただ、 OCaml はこの選択をした、そいう事だ。 前回の「経験15年の OCaml ユーザーが Haskell を仕事で半年使ってみた」 http://d.hatena.ne.jp/camlspotter/20101212/1292165692 のような易しい文章ではないのでわからない人はとことん判らないだろう。まあ勘弁して欲しい。 あと、面倒だろうが、読む人は全部常体を敬体にして最後に「と思います」をつけて読んでくれ。ください、と思います。 Shadowing は便利であると思っている OCaml の let は非再帰なので以前定義された名前に別の値の束縛をオーバーライドできる。OCaml の人はこれが便利だと思っており皆普通に使っている。詳しくは http://d.hat
右も左も分かる再帰 - あどけない話
「函数プログラミングの集い」のチュートリアル資料を作成するためのメモ。リストに対する再帰を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
https://github.com/kazu-yamamoto/recursion-drill/blob/master/README.md