IT練習ノート

IT関連で調べたこと（実際は嵌ったこと）を書いています。

Haskellで最小値と最大値を同時に(one pass)求める

Haskell

モノイドを学習をしているときに、モノイドのインスタンスがあれば、複数のモノイドを同時に計算ができて、スゲーなと思いました。じゃあ、minとmaxのモノイドを作れば同時に求めることができるだろうと思って試行錯誤したことがあります。こちらのエントリが参考になります。 http://www.markhneedham.com/blog/2012/05/28/haskell-finding-the-minimum-maximum-values-of-a-foldable-in-one-pass/

別の機会に、すごいH本のアプリカティブのsequenceA解説を Functors, Applicative Functors and Monoids - Learn You a Haskell for Great Good! 読み直していたとき(実際は訳書を読んでいた訳ですが)に、アプリカティブでも同じことができる気がして試したところできました。

sequenceAを作るのも面倒なのでsequenceでやってみました。

まずは型の確認

  • foldr1の型
*Main> :t foldr1
foldr1 :: (a -> a -> a) -> [a] -> a
  • minの型
*Main> :t min
min :: Ord a => a -> a -> a
  • foldr1 minの型
*Main> :t foldr1 min
foldr1 min :: Ord a => [a] -> a
  • [foldr1 min]の型
*Main> :t [foldr1 min]
[foldr1 min] :: Ord a => [[a] -> a]
  • [foldr1 min, foldr1 max]の型
*Main> :t [foldr1 min, foldr1 max]
[foldr1 min, foldr1 max] :: Ord a => [[a] -> a]
  • sequenceの型
*Main> :t sequence
sequence :: Monad m => [m a] -> m [a]
  • sequenceと[foldr1 min, foldr1 max]を合成する。
*Main> :t sequence [foldr1 min, foldr1 max]
sequence [foldr1 min, foldr1 max] :: Ord a => [a] -> [a]
*Main>

Control/Monad.hs を確認すると、

Evaluate each action in the sequence from left to right, and collect the results.

となっているので、 foldr1 min, foldr maxを順番に実行しているのはわかるのですが、

型に着目したときに、[a] -> [a]になるかが理解できず。

  1. 記号が重なるとわかりにくいので、一旦、[[a] -> a]を[[b] -> b]に変える。
  2. [m a] -> m [a] の 左辺の[m a]が[[b] -> b]に対応する。
  3. []を取り払うと、m a が [b] -> bに対応する。
  4. 中間演算子を前置にかえると、(->) [b] b
  5. だから、m a のmは(->[b])でm a のaはb。
  6. この対応を、[m a] -> m [a] 右辺の型に当てはめると m [a]は((->)[b]) [b]
  7. 中間演算子で表すと、[b]->[b]。

上記の5.のモナドは下記での一番最後のインスタンスのこと。

*Main> :i Monad
class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a
    -- Defined in `GHC.Base'
instance Monad (Either e) -- Defined in `Data.Either'
instance Monad Maybe -- Defined in `Data.Maybe'
instance Monad [] -- Defined in `GHC.Base'
instance Monad IO -- Defined in `GHC.Base'
instance Monad ((->) r) -- Defined in `GHC.Base'

この理解で合っているのだろうか？？？

  • 実行してみる。
*Main> sequence [foldr1 min, foldr1 max] [1..100]
[1,100]
*Main> sequence [foldr1 min, foldr1 max] [1,100,2,30,5]
[1,100]
*Main> sequence [foldr1 min, foldr1 max] [1,100,2,302,5]
[1,302]
*Main> sequence [foldr1 min, foldr1 max] [10,100,2,302,5]
[2,302]
*Main>