concat実装

myconcat :: [[a]] -> [a]
myconcat = foldr (++) []

Real World Haskell―実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。

4章の練習問題

Real World Haskell―実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。

1

import Data.Char (digitToInt)

asInt_fold :: String -> Int
asInt_fold cs@(c:cs') | c == '-'  = negate $ foldl step 0 $ map digitToInt cs'
                      | otherwise = foldl step 0 $ map digitToInt cs
                      where step x y = 10*x + y


-- *Main> asInt_fold "101"
-- 101
-- *Main> asInt_fold "-31337"
-- -31337
-- *Main> asInt_fold "1798"
-- 1798

2

-- 2
import Data.Char (digitToInt)

asInt_fold :: String -> Int
asInt_fold [] = 0
asInt_fold "-" = 0
asInt_fold cs@(c:cs') | c == '-'  = negate $ foldl step 0 $ map digitToInt cs'
                      | otherwise = foldl step 0 $ map digitToInt cs
                      where step x y = 10*x + y

-- *Main> asInt_fold ""
-- 0
-- *Main> asInt_fold "-"
-- 0
-- *Main> asInt_fold "-3"
-- -3
-- *Main> asInt_fold "2.7"
-- *** Exception: Char.digitToInt: not a digit '.'
-- *Main> asInt_fold "314159265358979323846"
-- 1537529798

3

なんか汚い。

import Data.Char (digitToInt,isDigit)
type ErrorMessage = String

asInt_fold :: String -> Either ErrorMessage Int
asInt_fold [] = Right 0
asInt_fold "-" = Right 0
asInt_fold cs@(c:cs') | c == '-'  = case foldl step (Right 0) cs' of
                                      Right x  -> Right  (negate x)
                                      Left x   -> Left x 
                      | otherwise = foldl step (Right 0) cs
                      where step (Left x) _ = Left x
                            step (Right x) y = case isDigit y of
                                                 True  -> Right (10*x + (digitToInt y))
                                                 False -> Left ("non-digit '" ++ [y] ++ "'")

RWHの4章にfoldlをfoldrによって書く例が載っていたのだけど、ぱっと見ただけではわからなかったので良く考えてみた。

Real World Haskell―実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

これは結局

foldr step id xs

によって出来た関数に本来の初期値であるzを与えていると。

例えば

myFoldl (+) 0 [1..3]

だと

foldr (+) id [1..3]

により

\x -> (+3) $ (+2) $ (+1) (id x)

が出来てこれに元の初期値0が与えられて(3+(2+(1+0)))となる。

参考

• Real World Haskell の 4.6.8 節の myFoldl