foldみぎひだり - Qiita
この記事は ML Advent Calendar 2015 の 7 日目の記事です。 ML 系言語を含め、多くの関数型言語はリストの畳み込み関数を持っている。動作についてはひとつの言語を知っていれば他の言語で困ることはないのだけれど、引数の取り方が違って迷うことがある。 リストの畳み込み リストの畳み込みと呼ばれる演算には右畳み込みと左畳み込みがあり、リスト [e1, e2, ..., en] と初期値 z、二項演算 ⊕ に対して以下のように定義される。 右畳み込み (e1 ⊕ (e2 ⊕ ... (en ⊕ z) ... )) 左畳み込み (( ... ((z ⊕ e1) ⊕ e2) ⊕ ...) ⊕ en) 右畳み込みはリストの右側の要素から順に取り出して初期値 z と組み合わせていき、左畳み込みはそれを左側の要素から行なう。 末尾呼び出しの最適化があれば、左畳み込みは固定のスタック領
λ Lessons
λ Lessons Pattern matching, first-class functions, and abstracting over recursion in Haskell This is a short, interactive lesson that teaches core functional programming concepts. It was designed to transform the way you think about performing operations on lists of things, by showing you how functions are executed. You can explore the way map and fold (foldr and foldl) are defined and computed. F
foldlを直す - 純粋関数空間
http://www.well-typed.com/blog/90/ foldlに関するこの記事（英文）が面白かったので、勝手翻訳しました。 foldlなんとかなるといいですね。 foldlを直す foldl 関数は壊れている。壊れているとみんなが知っている。 四半世紀近く壊れたままだ。ついにこれを修正する時が来た！ 今日、私はPrelude.foldlをData.List.foldl'として知られる実装で再定義することを提案する。 foldlは壊れている！ 既にご存知だとは思うが、念のため… Haskellerが必ずfoldlではなく、foldrやfoldl'を使うように勧めてくることにお気づきだろうか？ 例えばReal World Haskellでは次のように言っている。 `foldl`のサンクの挙動のため、実アプリではこの関数を使わないようにするのが望ましい。 特に問題がない場合でも
Fixing foldl
The foldl function is broken. Everyone knows it’s broken. It’s been broken for nearly a quarter of a century. We should finally fix it! Today I am proposing that Prelude.foldl be redefined using the implementation currently known as Data.List.foldl'. foldl is broken! I’m sure you knew that already, but just in case… Have you ever noticed that Haskellers usually recommend using either foldr or fold
fold_leftとfold_rightが同じになるとき - にわとり小屋でのプログラミング
fold_leftとfold_rightの結果が同じになるときが気になったので少し調べてみた。 例えば文字列のリストを連結して一つの文字列を生成する次の例はfold_leftでもfold_rightでも同様に定義できて同じ関数になる。Coqで書くと次のような感じ。 Definition xs := "foo" :: "bar" :: "baz" :: nil. Eval compute in (fold_left append xs ""). Eval compute in (fold_right append "" xs). fold_leftとfold_rightの定義はそれぞれ次のとおり Section Fold_Left_Recursor. Variables A B : Type. Variable f : A -> B -> A. Fixpoint fold_left (l:l
Scalaでコレクションを並列に畳み込む - CLOVER🍀
いや、Scalaに詳しい人からすると当たり前かもしれませんが、今まで知らなかったので…。 通常、Scalaで例えばListの和を求めようと思うとfoldLeftとかreduceLeftとかを使うと思いますが、並列コレクションを使った場合って、これって並列に実行されると困りますよね？ 実際、scala.collection.parallel.ParIterableLike.scalaを見ると、単純にオリジナルのシーケンスの各メソッドを呼んでいるだけになります。 // Source from Scala 2.9.2 ... def foldLeft[S](z: S)(op: (S, T) => S): S = seq.foldLeft(z)(op) def foldRight[S](z: S)(op: (T, S) => S): S = seq.foldRight(z)(op) def red
GenTraversable の fold が結合法則を満たさなければならない理由 - xuwei-k's blog
タイトルに関する言い訳 みずしまさんに突っ込まれて、その後のtwitter上でのやり取りもあったので、下に追記したよ！ ウオーーッ scala の GenTraversable#fold 今まで foldl1 のつもりで使ってたけど "a binary operator that must be associative" と書いてあるヨ???歳納さん、歳納さんーー 2012-09-15 01:52:51 via web @lyrical_logical foldってたしか2.8以前は存在しなくて、2.9でparallel collectionが入った関係で追加されたから、そんな感じになっていたとかだったような(だいぶ憶測で言ってるから間違ってるかも) 2012-09-15 02:05:21 via web to @lyrical_logical .@lyrical_logical URL
リストの畳み込みと展開 - あどけない話
リストの畳み込みには、foldr が使われる。 foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ ini [] = ini foldr op ini (x:xs) = x `op` foldr op ini xs Data.List には、この双対となる関数 unfoldr が定義してある。 unfoldr :: (a -> Maybe (b,a)) -> a -> [b] unfoldr f x = case f x of Nothing -> [] Just (z,x') -> z : unfoldr f x' unfoldr は種からリストを生成する。 既存の関数 unfoldr をプリミティブと考えて、他の関数を定義してみる。まずは、iterate。 iterate :: (a -> a) -> a -> [a] iterate f =
foldLeft と foldRight のエイリアス - A Memorandum
foldLeft 初期値を1として、arrの和を得る。 val arr = List(2, 3, 4) arr.foldLeft(1){(x, y) => x + y} 1 + 2 + 3 + 4 で 10 となる。 短く書くと、 arr.foldLeft(1)( _ + _ ) foldLeft には /: というエイリアスがあり、以下のように書ける。 (1 /: arr){_ + _} foldRight foldRight では適用の順番が逆になる。 val arr = List(2, 3, 4) arr.foldRight(1)( _ + _ ) 4+1 3+(4+1) 2+(3+(4+1)) の順番で適用される。 foldRight は :\ というエイリアスがあり、以下のように書ける。 (arr :\ 1){_ + _} foldLeft の /: とは引数の位置が逆になる。末
畳み込み関数の比較 (fold / accumulate / inject / reduce) - blanket log
つーか、fold の弱点として、言語によって引数の順番がまちまちで、 正直憶えきれないってのがあるんだよな。誰か対応表とか作ってくれんもんか。 jijixi's diary - fold, map, for-each この中から一つ選ぶとしたらどれ？ 確かにいろいろとややこしいのでまとめてみました。 いくつかの言語について大雑把に表にすると次のような感じ。 言語 関数 Haskell, OCaml, Scheme, Erlang foldl* f init items C++ accumulate(begin, end, init, f) Ruby*, JavaScript items.inject(init, f) Python, Perl* reduce(f, items [, init]) 言語 畳み込む二項演算 Scheme(SRFI)*, Erlang f(item, acc)
Introduction to Categorical Programming (Revised)
The document contains chemical structures and mathematical equations. It discusses machine learning methods for predicting molecular properties from graph-based representations of molecules using node and edge descriptors without quantum chemistry calculations. Random forest, support vector machines, and other models are mentioned for making predictions from molecular graph encodings.
What's Wrong with the For Loop
Closures in Java are a hot topic of late. A few really smart people are drafting a proposal to add closures to a future version of the language. However, the proposed syntax and the linguistic addition are getting a lot of push back from many Java programmers. Today, Elliotte Rusty Harold posted his doubts about the merits of closures in Java. Specifically, he asks "Why Hate the for Loop?": I don’
foldr のすごさを体験してみた - melpon日記 - HaskellもC++もまともに扱えないへたれのページ
Real World Haskell にはこんなコードが載ってます。 myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f z xs = foldr step id xs z where step x g a = g (f a x) Real World Haskell p100 4.6.8 右からの畳み込み foldl は foldr を使って書けるという例です。 こんな風にほとんどのリスト処理は再帰を使わなくても foldr を使えば書けるらしい*1ので、どこまでできるのか確認するために Prelude にある Data.List の関数を再定義してみました。 ルールは、 再定義した関数は直接的または間接的に再帰していてはならない（foldr は除く） 再帰しないで作った関数を他の関数で使うのは OK 再定義した関数は元の関数と同じ計算
右も左も分かる再帰 - あどけない話
「函数プログラミングの集い」のチュートリアル資料を作成するためのメモ。リストに対する再帰を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
関数型！侵略ノススメ☆ - 純粋関数型雑記帳
（この記事は Functional Ikamusume Advent Calendar jp 2010 の為に書かれました） 侵略！侵略！侵略！侵略！侵略！侵略！イカ娘！ 再帰しなイカ？ main = putStrLn $ f 6 where f 0 = "イカ娘！" f n = "侵略！" ++ f (n-1) 古風に再帰しなイカ？ main = putStrLn $ f 6 where f 0 = "イカ娘！" f (n+1) = "侵略！" ++ f n 左派じゃなイカ？ main = putStrLn $ foldl (\a _ -> "侵略！"++a) "イカ娘！" [1..6] 右派じゃなイカ？ main = putStrLn $ foldr (\_ a -> "侵略！"++a) "イカ娘！" [1..6] 右派に見せかけた左派じゃないか？ main = putStrLn $
途中脱出のある反復計算 - HaHaHa!
そのまえに もとネタは[id:Dekosuke:20100810]「breakのあるfor文をHaskellで書きなおす」という記事です． この記事に対して，直感的に[id:nobsun:20100118]の双方向畳み込みfoldで汎用的に表現できる」と思って，コメントを付けました．ところが，その後が波瀾万丈 < 大袈裟なやつ 途中脱出の例題を考えてみた． ちゃちゃっと書いたサンプルコードが途中脱出してくれない． あわてて取り消しのコメントを． どうも原因がよくわからない，上手くいくはずなのに． foldの定義の所為だと思い込む． 何人かにfoldを説明してみた． coolじゃないfoldの代替定義をでっちあげた． 代替foldリファクタリング． 代替foldを何人かに説明してみた． 代替foldでよいことは納得できる． でもやっぱり，元のfoldで上手くいかなり理由がわからない． よくよ
Beautiful folding
> {-# LANGUAGE ExistentialQuantification #-} > import Data.List (foldl') If you're not a Haskeller, and were thus hoping to learn how to fold a shirt beautifully, I'm afraid you're out of luck. I don't know either. Much has been said about writing a Haskell function to calculate the mean of a list of numbers. For example, see Don Stewart's "Write Haskell as fast as C". Basically, one wants to writ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Monoid&Foldable版intersperseとか - Qiita
https://qiita.com/minpou/items/34a67281b4b746bc5fcc
azito.com