Haskellが単純な問題をどのように困難にするかについて、多くの例があります。 おそらく最も有名なのはエラトステネスのふるいです。これは命令型言語で書くのは簡単ですが、Haskellで書くのは非常に難しいので、大学で教えられ、過去18年間の研究で使用されたほとんどすべてのソリューションが間違っていることが判明しました。 彼らの失敗は、彼の重要な科学作品「 エラトステネスの本当のふるい 」でメリッサ・オニール（メリッサ・オニール）の注目を集めました。 古いアプローチの何が悪いのか、どのように修正するのかについての優れた説明を提供します。 メリッサの解決策は、優先キューを使用してふるいを実装することでした。 正しい解決策は、F＃のより単純な解決策よりも10倍長く、Haskellの元の変形アルゴリズムよりも100倍長いことが判明しました。
今日、迅速な選別はエラトステネスの新しいふるいです。 そして、Haskellプログラマーは、言語がこのアルゴリズムを無効にすることでこのアルゴリズムを表現できないことを再び回避しました。 新しいバージョンははるかに低速ですが、Haskellで簡単に記録できます。
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
このコードは、実際のクイックソートアルゴリズムの本質と完全に矛盾しており、非常に効率的です（高速ソートに関するトニーホアーのオリジナル記事1962を参照）。 つまり、追加のメモリ割り当てなしでアレイをパーティション分割する[スワップを使用したインプレースパーティション分割]。
Haskellで汎用並列並列クイックソートを作成する問題に直面して、Jim Apple（カリフォルニア大学デイビス校、カリフォルニア大学デイビス校でHaskell Ph.D.を書いている）は、次のコードを書くことでケースを開始しました。
import Data.HashTable as H import Data.Array.IO import Control.Parallel.Strategies import Control.Monad import System exch air = do tmpi <- readArray ai tmpr <- readArray ar writeArray ai tmpr writeArray ai tmpi bool abc = if c then a else b quicksort arr lr = if r <= l then return () else do i <- loop (l-1) r =<< readArray arr r exch arr ir withStrategy rpar $ quicksort arr l (i-1) quicksort arr (i+1) r where loop ijv = do (i', j') <- liftM2 (,) (find (>=v) (+1) (i+1)) (find (<=v) (subtract 1) (j-1)) if (i' < j') then exch arr i' j' >> loop i' j' v else return i' find pfi = if i == l then return i else bool (return i) (find pf (fi)) . p =<< readArray arr i main = do [testSize] <- fmap (fmap read) getArgs arr <- testPar testSize ans <- readArray arr (testSize `div` 2) print ans testPar testSize = do x <- testArray testSize quicksort x 0 (testSize - 1) return x testArray :: Int -> IO (IOArray Int Double) testArray testSize = do ans <- newListArray (0,testSize-1) [fromIntegral $ H.hashString $ show i | i <- [1..testSize]] return ans
このアルゴリズムは、Haskellの並列「 戦略 」を使用します。 この概念は、Haskellプログラマーが並列化をより細かく制御できるようにするために開発されましたが、利用可能な実装はメモリのみであり 、誰もこのコードで動作させることができなかったことがわかりました：Jimのソリューションにはマルチスレッドエラー[同時実行性]が含まれているため、ほとんどすべての呼び出しで誤った結果を返します。
次に、PekerはHaskellで彼のソリューションを提案しました 。
import Data.Array.IO import Control.Monad import Control.Concurrent bool t _f True = t bool _t f False = f swap arr ij = do (iv, jv) <- liftM2 (,) (readArray arr i) (readArray arr j) writeArray arr i jv writeArray arr j iv parallel fg bg = do m <- newEmptyMVar forkIO (bg >> putMVar m ()) fg >> takeMVar m sort arr left right = when (left < right) $ do pivot <- read right loop pivot left (right - 1) (left - 1) right where read = readArray arr sw = swap arr find n pred i = bool (find n pred (ni)) (return i) . pred i =<< read i move op di pivot = bool (return op) (sw (d op) i >> return (d op)) =<< liftM (/=pivot) (read i) loop pivot oi oj op oq = do i <- find (+1) (const (<pivot)) oi j <- find (subtract 1) (\idx cell -> cell>pivot && idx/=left) oj if i < j then do sw ij p <- move op (+1) i pivot q <- move oq (subtract 1) j pivot loop pivot (i + 1) (j - 1) pq else do sw i right forM_ (zip [left..op-1] [i-1,i-2..]) $ uncurry sw forM_ (zip [right-1,right-2..oq+1] [i+1..]) $ uncurry sw let ni = if left >= op then i + 1 else right + i - oq nj = if right-1 <= oq then i - 1 else left + i - op let thresh = 1024 strat = if nj - left < thresh || right - ni < thresh then (>>) else parallel sort arr left nj `strat` sort arr ni right main = do arr <- newListArray (0, 5) [3,1,7,2,4,8] getElems arr >>= print sort (arr :: IOArray Int Int) 0 5 getElems arr >>= print
この解決策もバグがありました。 まず、より微妙な並行性のバグが含まれており、これはたまに誤った結果をもたらします。 ピッカーは、次のコードのこのバグを修正しました。
import System.Time import System.Random import Data.Array.IO import Control.Monad import Control.Concurrent import Control.Exception import qualified Data.List as L bool t _ True = t bool _ f False = f swap arr ij = do (iv, jv) <- liftM2 (,) (readArray arr i) (readArray arr j) writeArray arr i jv writeArray arr j iv background task = do m <- newEmptyMVar forkIO (task >>= putMVar m) return $ takeMVar m parallel fg bg = do wait <- background bg fg >> wait sort arr left right = when (left < right) $ do pivot <- read right loop pivot left (right - 1) (left - 1) right where read = readArray arr sw = swap arr find n pred i = bool (find n pred (ni)) (return i) . pred i =<< read i move op di pivot = bool (return op) (sw (d op) i >> return (d op)) =<< liftM (/=pivot) (read i) swapRange px x nx y ny = if px x then sw xy >> swapRange px (nx x) nx (ny y) ny else return y loop pivot oi oj op oq = do i <- find (+1) (const (<pivot)) oi j <- find (subtract 1) (\idx cell -> cell>pivot && idx/=left) oj if i < j then do sw ij p <- move op (+1) i pivot q <- move oq (subtract 1) j pivot loop pivot (i + 1) (j - 1) pq else do sw i right nj <- swapRange (<op) left (+1) (i-1) (subtract 1) ni <- swapRange (>oq) (right-1) (subtract 1) (i+1) (+1) let thresh = 1024000 strat = if nj - left < thresh || right - ni < thresh then (>>) else parallel sort arr left nj `strat` sort arr ni right timed act = do TOD beforeSec beforeUSec <- getClockTime x <- act TOD afterSec afterUSec <- getClockTime return (fromIntegral (afterSec - beforeSec) + fromIntegral (afterUSec - beforeUSec) / 1000000000000, x) main = do let n = 1000000 putStrLn "Making rands" arr <- newListArray (0, n-1) =<< replicateM n (randomRIO (0, 1000000) >>= evaluate) elems <- getElems arr putStrLn "Now starting sort" (timing, _) <- timed $ sort (arr :: IOArray Int Int) 0 (n-1) print . (L.sort elems ==) =<< getElems arr putStrLn $ "Sort took " ++ show timing ++ " seconds"
このソリューションは小さな入力配列で動作しますが、配列のサイズを1,000,000要素に増やすとスタックがオーバーフローします。 このバグを分析するためにhereとhereの 2つの試みが行われましたが、どちらも間違っていることが判明しました。 これは実際には、 Haskell標準ライブラリのgetElems関数のバグであり、大きな配列のスタックをオーバーフローさせます。
奇妙なことに、さらにいくつかのバグの修正により、明らかに、Haskellで書かれた世界初の並列汎用クイックソートが実装されました。 さらに、Haskellの最終的なソリューションは、F＃の同等のソリューションよりも約55％遅いだけです。 このソリューションには、数週間前にリリースされた最新バージョンのGHCが必要です （ 約Pere。：2010年の記事。したがって、読者は心配する必要はありません ）。
元の記事に対する最初のコメント
ガネーシャ・シタンパラム：
Haskellでフォークと同期を行う方法を学習できたことをお祝いします！
ジョンハロップ（元の著者）：
「自明」になるという理論をテストしていただき、ありがとうございます...