[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part4 (1001ﾚｽ)

関数型プログラミング言語Haskell Part4 http://echo.5ch.net/test/read.cgi/tech/1140717775/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

684: デフォルトの名無しさん [sage] 2006/05/01(月) 10:57:31 二分探索を書こうとしたのだが、どうも上手くできない。 --リストの中央インデックスを求める middle :: [a] -> Int middle [] = -1 middle x = (ceiling half) - 1 where half = fromIntegral (length x) / fromIntegral 2 --リストの中央値を返す median :: [a] -> a median x = x !! (middle x) bsearch k [] = -1 bsearch k x | median x > k = bsearch k (take (middle x) x) | median x == k = middle x | median x < k = middle x + 1 + bsearch k (drop ((middle x)+1) x) 「bsearch k [] = -1」が悪いのはわかってるんだが、 うまく動くよう記述する方法がわかんない。 どうすればいい？ http://echo.5ch.net/test/read.cgi/tech/1140717775/684

685: デフォルトの名無しさん [sage] 2006/05/01(月) 11:13:45 >>684 bsearchの最後の等式で、再帰的に呼ばれたbsearchが-1を返したときにまずいことになる。 これを防ぐには、結果が-1かどうかを明示的にテストすればいい。 bsearch k [] = -1 bsearch k x    | median x > k  = bsearch k (take (middle x) x)    | median x == k = middle x    | median x < k  = case bsearch k (drop ((middle x)+1) x) of     -1 -> -1     r -> middle x + 1 + r 以下、本題とは関係ないけど、 ・Haskellではbsearchのような「失敗する可能性のある」関数の結果はMaybeでラップするのが普通。 失敗時に-1を返すよりNothingを返した方が直感的だし、間違いも少ない。 ・ceiling (fromIntegral (length x) / fromIntegral 2) は div (length x) 2と書ける。 http://echo.5ch.net/test/read.cgi/tech/1140717775/685

965: デフォルトの名無しさん [sage] 2006/06/02(金) 03:04:27 亀レスですまんが、 >>684 Haskellのリストで二分検索ってできるの？ 二分検索というからにはO(logN)じゃないと意味がないと思うんだが、 lengthだの!!だの使っている時点でO(N)を越えている気がしてならない。 http://echo.5ch.net/test/read.cgi/tech/1140717775/965

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.031s