はてなブックマーク

この記事は検証待ちです。 計測結果および「入力と出力をUnboxed Vectorにすれば、途中がリストでもUnboxed型の恩恵を得られる」を除く結論については、計測ミスの結果である事が分かっています。 再計測ができ次第、記事をアップデートします。 Haskellの入門者向け解説ではHaskellのエレガントさのデモンストレーションとして、以下のように非常にシンプルなクイックソートが紹介される事があります。 quicksort [] = [] quicksort (x:xs) = quicksort lt ++ [x] ++ quicksort gteq where lt = filter (<x) xs gteq = filter (>=x) xs しかし、このソートは「遅い」「というかクイックソートじゃない」と、批判の対象になっています。 https://togetter.com/l

この記事は、Haskell (その2) Advent Calendar 2017 の4日目の記事です。 同アドベントカレンダーの5日目の記事、しりとりの圏の実装(未完) の問題を解いてみたのと、その際に定理証明Haskellのちょうどいい例題が出て来たので、解説してみます。 なお4日目の記事が5日目の記事のアンサーになるのは時空間の歪みによるもので正常な動作です。日付順に読まれている方については、申し訳ございませんが5日目の記事に飛んでいただけるようお願い致します。 idを定義するために さしあたって、しりとりの圏を構成するSiriの定義を、親記事より拝借します。 {-# LANGUAGE DataKinds #-} {-# LANGUAGE GADTs #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE TypeApplications #-

しかし、criterionのエンジンは、計測コードを複数回実行し平均を取る仕組みになっています。そのため、二回目以降はソート済みの配列に対して時間計測を行ってしまっていました。 今回の配列ソートではピボットを中央から取っているため、ソート済みの配列に対しては最大効率になります。つまり前回記事の計測スコアでは、Vector関係は実際より良い数値が出てしまっている事になります。 という訳で、毎回のテストごとに初期化処理を入れるように修正します。 これを行うのは、以下の関数になります。 型を見ればおおよそ使い方が想像できると思いますが、第一引数のIOアクションにより、env型の値を計測外で作成し、それを引数として計測を実施します。 envはNFDataのインスタンスである必要があります。NFDataはseqによく似た、値の簡約を促す関数rnfを公開するクラスです。seqではリスト等の構造に対して

{-# LANGUAGE MultiWayIf #-} module Main where import Control.FRPNow import Data.Functor ((<$), (<$>)) import Control.Monad (join) streaming :: (EvStream a -> Behavior (EvStream b, Event ())) -> IO a -> ([b] -> IO ()) -> IO () streaming b ioA ioB = runNowMaster $ do (esA, cbA) <- callbackStream (esB, evE) <- sampleNow (b esA) loop cbA esB return evE where loop cbA esB = do eys <- sampleNow (nextAll

バックナンバー Arrow化pipeはFRPの夢を見るか？ 本記事も引き続き、Arrow記法対応のpipe系(ないしはIteratee系)自作ライブラリmachinecellの紹介です。 machinecell: Arrow based stream transducers 今回はインパクト重視のデモとして、小さなGUIプログラムを披露します。 その前にイントロとして、なぜIteratee系のライブラリをArrow化したか、というモチベーションの部分について、前回の記事より少し突っ込んで触れてみようと思います。 イントロ：Arrow化のモチベーション Iteratee系ライブラリとは、データを読み、書き、副作用を実行する小さな部品を「あたかもUnixのパイプのごとく」連ねて、一連の処理を行う事ができる「機能」を提供するものでした。 ArrowとはCategoryの拡張で、「あたかもパイプの

askP = P.constructT P.kleisli0 $ do lift $ putStrLn "情報を入力して下さい" forever $ do lbl <- P.await lift $ putStr (lbl ++ ": ") ct <- lift $ getLine P.yield (lbl, ct) registerP = do r <- runKleisli (P.run askP) ["Zip code", "Address", "Name"] print r ほとんど間違い探しのレベルですね。真似して作ったので仕方ない。machinecell側にだけkleisliという見慣れない名前が見えますが、これは型合わせだと思って無視して頂いてOKです。 上のコードは、ちょっと変則的ですが、pipe系の汎用性をデモするために「データの中間加工時に副作用を起こす処理」を実装して