Haskell で線形探索(番兵)
同じように配列に対する線形探索を書いた。Haskell のリストをわざわざメモリ上に保存しなおしているという無駄があるがサンプルなので気にしないことにする。
linearSearch :: (Eq a, Storable a) => a -> [a] -> IO (Bool, Int) linearSearch target xs = let n = length xs in do p <- mallocArray (n + 1) mapM_ (\(x, i) -> pokeElemOff p i x) (zip xs [0..]) pokeElemOff p n target -- 番兵 i <- search p target 0 if i == n then return (False, i) else return (True, i) where search p x i = do y <- peekElemOff p i if x == y then return i else search p x (i + 1)
Haskell でStackを(3)
今度はスタックのサイズは固定、要素もIntのみで、状態モナドを止めてみた。スタック自身でポインタを管理する。これで複数のスタックを使える。ほぼCの構造体になったと思うがわたしはCを書けないので自信なし。
import Foreign.Ptr import Foreign.Marshal.Alloc import Foreign.Marshal.Array import Foreign.Storable stackSize :: Int stackSize = 20 -- スタックのインデックスとスタック本体へのポインタ data Stack = Stack Int (Ptr Int) deriving Show instance Storable Stack where alignment _ = 16 sizeOf _ = 16 peek ptr = do n <- peek (castPtr ptr) p <- peek (castPtr ptr `plusPtr` 8) return $ Stack n p poke ptr (Stack n p) = do poke (castPtr ptr) n poke (castPtr ptr `plusPtr` 8) p mkStack :: IO (Ptr Stack) mkStack = do p <- malloc :: IO (Ptr Stack) s <- mallocArray stackSize poke p (Stack 0 s) return p push :: Ptr Stack -> Int -> IO (Ptr Stack) push st x = do Stack i p <- peek st if i >= stackSize then error "oops. Stack overflow" else do pokeElemOff p i x poke st (Stack (i + 1) p) return st pop :: Ptr Stack -> IO Int pop st = do Stack i p <- peek st if i <= 0 then error "oops. Stack underflow" else do x <- peekElemOff p (i - 1) poke st (Stack (i - 1) p) return x calc :: (Int -> Int -> Int) -> Ptr Stack -> IO (Ptr Stack) calc f st = do x <- pop st y <- pop st push st (f x y) add :: Ptr Stack -> IO (Ptr Stack) add = calc (+) sub :: Ptr Stack -> IO (Ptr Stack) sub = calc (-)
使い方はこのように変わる。
test0 = do st <- mkStack push st 9 pop st
Haskell でスタックを(2)
Haskell でスタックを書く、続き。スタックのサイズは固定のまま、スタックの要素を変更できるようにした。
-- Stack import Control.Monad.State import Foreign.Ptr import Foreign.Marshal.Alloc import Foreign.Marshal.Array import Foreign.Storable stackSize :: Int stackSize = 20 initStack :: Storable a => IO (Ptr a, Int) initStack = do p <- mallocArray stackSize return (p, 0) -- https://www.haskell.org/haskellwiki/Scoped_type_variables より sizeOfPtr :: (Storable a) => Ptr a -> Int sizeOfPtr = sizeOf . (undefined :: Ptr a -> a) push :: (Storable a, Num a) => a -> StateT (Ptr a, Int) IO () push x = do (stack, sp) <- get if sp >= stackSize then error "oops. Stack overflow" else do lift $ pokeElemOff stack sp x put (stack, sp + 1) return () pop :: (Storable a, Num a) => StateT (Ptr a, Int) IO a pop = do (stack, sp) <- get if sp > 0 then do x <- lift $ peekElemOff stack (sp - 1) put (stack, sp - 1) return x else error "oops. Stack undeflow" calc :: (Storable a, Num a) => (a -> a -> a) -> StateT (Ptr a, Int) IO () calc f = do x <- pop y <- pop push (f x y) add :: (Storable a, Num a) => StateT (Ptr a, Int) IO () add = calc (+) sub :: (Storable a, Num a) => StateT (Ptr a, Int) IO () sub = calc (-)
以下のように使う。
-- initStack >>= runStateT test0 test0 :: StateT (Ptr Int, Int) IO Int test0 = do push 9 pop test1 :: StateT (Ptr Int, Int) IO () test1 = do push 3 push 99 x <- pop lift $ putStrLn $ "x: " ++ show x y <- pop lift $ putStrLn $ "y: " ++ show y test2 :: StateT (Ptr Int, Int) IO Int test2 = do push 8 push 9 pop pop push 11 push 13 pop pop test4 :: StateT (Ptr Float, Int) IO Float test4 = do push 5.0 push 7.0 push 8.0 add sub pop
参考
- 「Haskellでスタックを利用した加減乗除の計算機を作ってみる」 http://kzfm.github.io/laskell/stackCalc.html 状態モナドを理解するのにとても参考になった、明快なスタックと状態モナドの説明。
Haskell でスタックを書く
Ptr, malloc の勉強のため Haskell でスタックを書いてみた。いろいろ間違っている可能性あり。
-- Stack import Control.Monad.State import Foreign.Ptr import Foreign.Marshal.Alloc import Foreign.Storable stackSize :: Int stackSize = 12 intSize :: Int intSize = sizeOf (undefined :: Int) push :: Int -> StateT (Ptr Int, Int) IO () push x = do (stack, sp) <- get if (sp >= stackSize) then error "Stack overflow" else do lift $ poke (stack `plusPtr` (sp * intSize) :: Ptr Int) x put (stack, sp + 1) return () pop :: StateT (Ptr Int, Int) IO Int pop = do (stack, sp) <- get if (sp > 0) then do x <- lift $ peek (stack `plusPtr` ((sp - 1) * intSize) :: Ptr Int) put (stack, sp - 1) return x else error "Stack undeflow" initStack :: IO (Ptr Int, Int) initStack = do p <- mallocBytes (stackSize * intSize) return (p, 0) -- 実行方法 -- initStack >>= evalStateT test0 test0 = do push 9 pop test1 = do push 3 push 99 x <- pop lift $ putStrLn $ "x: " ++ show x y <- pop lift $ putStrLn $ "y: " ++ show y test2 = do push 8 push 9 pop pop push 11 push 13 pop pop
参考
以下のリンクに必要な情報は全てある。
- sirocco の書いてもすぐに忘れるメモ「Foreign.Marshal.Alloc.malloc、Foreign.Storable.peek、pokeを使ってみる。」http://d.hatena.ne.jp/sirocco/20130419/1366322756
- あどけない話 Haskell ポインタープログラミング http://d.hatena.ne.jp/kazu-yamamoto/20131225/1387938629
- 「Super Technique 講座 スタック」http://www.nurs.or.jp/~sug/soft/super/stack.htm C のスタック。この記事以外もとても分かりやすい。
Emacs M-| (shell-command-on-region)
メモ
;; バッファを対象にした shell-command-on-region (defun shell-command-on-buffer (command) (interactive (let (string) (list (read-shell-command "Shell command on buffer: ")))) (shell-command-on-region (point-min) (point-max) command nil nil nil t))
Haskell graphviz 関連
Hackage で graphviz 関連を検索したもの(http://hackage.haskell.org/packages/search?terms=graphviz)。
- graphviz ライブラリ http://hackage.haskell.org/package/graphviz 最終更新日: 2014/5/19 Data.GraphViz
- vacuum-graphviz ライブラリ http://hackage.haskell.org/package/vacuum-graphviz 最終更新日: 2012/9/15 vacuum graph を graphviz に変換 GHC.Vacuum.GraphViz
- xdot ライブラリ http://hackage.haskell.org/package/xdot 最終更新日: 2014/5/23 Graphics.XDot
- vacuum-cairo ライブラリ http://hackage.haskell.org/package/vacuum-cairo 最終更新日: 2011/2/15 System.Vacuum.Cairo
- language-dot ライブラリ http://hackage.haskell.org/package/language-dot 最終更新日: 2012/10/9 Language.Dot Dot ファイルの解析と生成。
- fgl-visualize ライブラリ http://hackage.haskell.org/package/fgl-visualize 最終更新日: 2013/5/16 Data.Graph.Inductive FGL グラフを Dot ファイルに変換。
- dot2graphml http://hackage.haskell.org/package/dot2graphml 最終更新日: 2013/7/3 Dot から GraphML への変換。
- vacuum-opengl http://hackage.haskell.org/package/vacuum-opengl 最終更新日: 2010/1/14 System.Vacuum.OpenGL
- hs2dot http://hackage.haskell.org/package/hs2dot 最終更新日: 2010/7/15 Haskell コードを解析して Dot へ変換。
- prof2dot http://hackage.haskell.org/package/prof2dot 最終更新日: 2008/8/4
- scons2dot http://hackage.haskell.org/package/scons2dot 最終更新日: 2010/2/24
- vacuum http://hackage.haskell.org/package/vacuum 最終更新日: 2014/5/13 GHC.Vacuum 実行時の GHC heap を可視化
- dotgen http://hackage.haskell.org/package/dotgen 最終更新日: 2009/10/6 Text.Dot Dot を生成
- flow2dot http://hackage.haskell.org/package/flow2dot 最終更新日: 2012/6/29 シーケンスダイアグラムを生成 Text.FlowDiagram
- math genealogy http://hackage.haskell.org/package/mathgenealogy 最終更新日: 2013/1/17 ?
- Emping http://hackage.haskell.org/package/Emping 最終更新日: 2009/5/29 ?
- graphtype http://hackage.haskell.org/package/graphtype 最終更新日: 2010/9/13 "This tools produces diagrams of Haskell type interdependencies in the given source."
- tamarin-prover http://hackage.haskell.org/package/tamarin-prover 最終更新日: 2014/6/8 "The Tamarin prover is a tool for the analysis of security protocols"
- dvda http://hackage.haskell.org/package/dvda 最終更新日: 2014/4/5 "dvda == DVDA Verifiably Differentiates Algorithmically"
- darcs2dot http://hackage.haskell.org/package/darcs2dot 最終更新日: 2013/4/7 "Outputs dependencies of darcs patches in dot format."
- fault-tree http://hackage.haskell.org/package/fault-tree 最終更新日: 2011/1/4 ?
- maxsharing http://hackage.haskell.org/package/maxsharing 最終更新日: 2014/2/3 "Parses a lambda-letrec term; transforms it into a first-order term graph representation; minimises the graph; reads back a lambda-letrec term which has the same unfolding as the original term, but exhibits maximal sharing. "
Monad Ambiguous type variable
例は IFPH 10章より。
data Term = Con Int | Div Term Term evalId (Con x) = return x evalId (Div t u) = do x <- evalId t y <- evalId u return (x `div` y)
上記は意図的に evalId の型を指定していない。型を調べると、
:t evalId evalId :: Monad m => Term -> m Int
と推論されていて、具体的なモナド(例えば Identity モナド) を指定しないと動かないように思える。実際、別の変数に束縛しようとするとエラーになる。にもかかわらず、ghci で実行すると実行できてしまう。
:t evalId (Con 13) => evalId (Con 13) :: Monad m => m Int let x = evalId (Con 0) => Ambiguous type variable m0 in the constraint: (Monad m0) arising from a use of evalId evalId (Con 13) => 13
これはいったい何が起きているのだろう?