『ファンクターからアプリカティブファンクターへ』　練習問題

Functerインスタンスを考える

次のもののFuncterインスタンスを考えてみよう。実装はファンクター則を満たしているだろうか。また、それ以外の実装はありえるだろうか。

data Maybe a     = Nothing | Just a

data [] a        -- リスト 

data Tree a      = Leaf | Branch a (Tree a) (Tree a) 

data Either a b  = Left a | Right b

data (,) a b     -- タプル

たとえばリストだったら、以下のように書く。

instance Functor [] where
  fmap f xs = undefined

ヒント：

次のMaybeのFuncter実装は、ファンクター則を満たしているだろうか。

instance Functor Maybe where
  fmap f Nothing  = Nothing
  fmap f (Just a) = Nothing

参考：The Typeclassopedia

ファンクター則を破るとどうなるの？

今、a, b, c, f, g の５つの関数の間に、次の恒等式が成り立っているとする。

-- a, b, c, f, g はすべて1引数関数と仮定してよい

g . f  == c . b . a

それぞれの関数をファンクターで写したとき、以下のような同じ恒等式が成り立つだろうか。ファンクター則が成り立つときと、成り立たないときについて、確認してみよう。

(fmap g) . (fmap f)  == (fmap c) . (fmap b) . (fmap a)

参考：ファンクター則は、一般的には準同型と呼ばれる。 ja.wikipedia.org/wiki/準同型

ファンクターを使って書き直す

次のコードをファンクターを使って書き直してみよう。

-- 1行読み込んで、空白区切りで分割して、1行ずつ表示する
main = do
  xs <- getLine
  let ws = words xs
  mapM_ putStrLn ws

-- 空白区切りの数字の列を1行読み込んで、その合計を表示する
main = do
  xs <- getLine
  let n = sum $ map read $ words xs
  print n

モナドをアプリカティブに書き直す

次のIOモナドを使ったコードを、アプリカティブスタイルに書き直してみよう。

main :: IO ()
main = do
  z <- add
  print z


add :: IO Int
add = do
  x <- readLn
  y <- readLn
  return (x+y)

次のコードもアプリカティブスタイルに書き直してみよう。

main :: IO ()
main = do
  putStrLn "What's your name?"
  name <- getLine
  putStrLn $ "Hello, " ++ name

パーサーコンビネータ

次のBNFを考える。

<formula> ::= 0 | 1 | 2 | 3 |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

これを解析して計算するパーサーコンビネーターをモナドスタイルで書いたのが次のコードである。これの number, minus, times, add 関数をアプリカティブスタイルに書き直してみよう。

import Text.ParserCombinators.Parsec
import Control.Applicative

main :: IO ()
main = do
  xs <- getLine
  case parse formula "" xs of
     Left err  -> print err
     Right n   -> print n

-- 簡単のため、全部に try を挟む
formula :: Parser Int
formula = choice $ map try [ number, minus, times, add ]

number :: Parser Int
number = do
  x <- choice [ char '0', char '1', char '2', char '3' ]
  return (read[x])

minus :: Parser Int
minus = do
  char '-'
  x <- formula
  return (-x)

times :: Parser Int
times = do
  char '('
  x <- formula
  char '*'
  y <- formula
  char ')'
  return (x * y)

add :: Parser Int
add = do
  char '('
  x <- formula
  char '+'
  y <- formula
  char ')'
  return (x + y)

実行例：echo "(2*3)" | runghc parser.hs

ヒント：Applicativeのススメに、アプリカティブを使ったパーサーコンビネーターの書き方が載っています。

Control.Applicativeにある、次の関数を駆使する必要があります。

-- 純粋な値を文脈へ持ち上げる（ただの a が 文脈f上に持ち上がって f a になった）
pure :: a -> f a

-- 文脈上で関数を適用する
(<*>) :: f (a -> b) -> f a -> f b

-- 第一引数を捨てる
(*>) :: f a -> f b -> f b

-- 第二引数を捨てる
(<*) :: f a -> f b -> f a

たとえば times 関数をアプリカティブに書き直すと、こんな感じです。

times :: Parser Int
times = (*)            -- 2引数関数を <$> で持ち上げて関数適用する
   　　　  <$> ((char '(' *> formula) <* char '*')  -- 真ん中以外は捨てる
   　　　  <*> (formula <* char ')') -- 第二引数は捨てる

出典：ACM国際大学対抗プログラミングコンテスト 2008 国内予選 問題C の改変

ZipList

ZipListを使って、Data.Listにあるtranspose関数を実装してみよう。

transpose :: [[a]] -> [[a]]

transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]

テキスト(p.253)にある sequenceA 関数と比較してみよう。

参考：Conor McBride and Ross Paterson. Applicative Programming with Effects. J. Funct. Program., 18(1):pages 1-13 (2008).