ふつうのHaskell勉強日誌
ふつうのHaskellプログラミング 初版 p246
練習問題 9.6
問題: 新しい型"Line"を定義し、sortLines関数でソートする
Line型は`data Lines = Lines {number::Int, string::String} deriving Show`で定義されるように、行番号とテキストで構成されます。
問題では、Data.Linesで定義されているsortByを使用することを推奨していますが、そうやって書いてもつまらないのでsortBy'を定義して問いてみました。
といっても、引数を関数を取るqsort関数を定義するだけですね。
module Main where main = do print $ sortLines mylines data Line = Line {number::Int, string::String} deriving Show mylines :: [Line] mylines = [Line 7 "piyo", Line 5 "hogehoge", Line 4 "fugafuga", Line 3 "piyo", Line 2 "fuga", Line 1 "hoge", Line 6 "piyopiyo"] sortLines :: [Line] -> [Line] sortLines = sortBy' (\(Line n _) (Line m _) -> compare n m) where sortBy' :: (a -> a -> Ordering) -> [a] -> [a] sortBy' _ [] = [] sortBy' f (piv:xs) = sortBy' f (filter (\x -> f x piv == LT || f x piv == EQ ) xs) ++ [piv] ++ sortBy' f (filter (\x -> f x piv == GT) xs) 出力: [Line {number = 1, string = "hoge"},Line {number = 2, string = "fuga"},Line {number = 3, string = "piyo"},Line {number = 4, string = "fugafuga"},Line {number = 5, string = "hogehoge"},Line {number = 6, string = "piyopiyo"},Line {number = 7, string = "piyo"}]
また、これも出題にはありませんでしたが、LineをOrd型クラスのインスタンスとすればもっとスマートではないかと思って下記の実装もしてみました。
module Main where main = do print $ qsort' mylines data Line = Line {number::Int, string::String} deriving (Show, Eq) instance Ord Line where compare (Line x _) (Line x' _) = compare x x' mylines :: [Line] mylines = [Line 7 "piyo", Line 5 "hogehoge", Line 4 "fugafuga", Line 3 "piyo", Line 2 "fuga", Line 1 "hoge", Line 6 "piyopiyo"] qsort' :: (Ord a) => [a] -> [a] qsort' [] = [] qsort' (piv:xs) = qsort' (filter (<= piv) xs) ++ [piv] ++ qsort' (filter (> piv) xs)
なお、この実装２つのの問題点として、「おなじnumberを持つLineが複数あった場合、それらのソート順序は考慮されない」というものが挙げられます。
通常、同一の行番号を持つLineが複数存在するということは考えられませんが
・同一の行番号を持つLineを排除する機構は作れるのか
・同一の行番号を持つLineのリストを許容した場合、「まず行番号でソートし、同一の行番号をもつ行同士は文字列でソートする」という実装はどう行なうか
が課題といえます。
アリンコの問題といた
職業プログラマがFizzBuzz書けない理由
タイトル: Ants
問題文: 長さL cmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。アリが竿の端に到達すると竿の下に落ちていきます。また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。各アリについて、現在の竿の左端からの距離xiはわかりますが、どちらの方向を向いているのかはわかりません。すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求めなさい。
制約: 1≦L≦106 1≦n≦106 0≦xi≦L
出典: プログラミングコンテストチャレンジブック(p.23) / 元はPOJ No.1852
むずかしいことはわからないけど、とりあえずHaskellでかいてみたよ。
distanceFromEdge :: Float -> Float -> Float distanceFromEdge l x | l < 0.0 || x < 0.0 || x > l = error "cant calc" | otherwise = if x < l * 0.5 then x else l - x ant :: Float -> [Float] -> (Float, Float) ant l [] = (l, 0) ant l (x:xs) = (minFromEdge, l - minFromEdge) where minFromEdge = min (distanceFromEdge l x) (fst (ant l xs)) ant' :: Float -> [Float] -> (Float, Float) ant' l xs = (minFromEdge, l - minFromEdge) where minFromEdge = minimum (map (distanceFromEdge l) xs) main = do putStrLn (show(ant 10.0 [5.0, 2.0, 8.0, 4.0, 1.5, 3.0])) => (1.5, 8.5)
引数が小文字Lだと|(vertical bar)と区別つかないですね。
まだHaskellのコードを読んだことがないので、"Haskellらしさ"がわからない。
なるべくその言語らしい書き方を心掛けたいけど、わからないからフワフワしてる。
distanceFromEdge
distanceFromEdge :: Float -> Float -> Float distanceFromEdge l x | l < 0.0 || x < 0.0 || l < x = error "cant calc" | otherwise = if x < l * 0.5 then x else l - x
インデントの作法がわからん。
ガード使う時って、"="の位置合わせたりするのかな。
if, elseは一行で書かないほうがいいのかな。
ant
ant :: Float -> [Float] -> (Float, Float) ant l [] = (l, 0) ant l (x:xs) = (minFromEdge, l - minFromEdge) where minFromEdge = min (distanceFromEdge l x) (fst (ant l xs))
とりあえず再帰でも使っとけばええんやろ？ちゃうの？的な安易な発想。
whereのインデントはいくつ置けばいいの。。
ant'
ant' :: Float -> [Float] -> (Float, Float) ant' l xs = (minFromEdge, l - minFromEdge) where minFromEdge = minimum (map (distanceFromEdge l) xs)
部分適用とか使ったら関数型っぽいんやろ？ちゃうの？的な安易な発想。
感想
インデントと改行の作法を求めて旅に出ます。
Objective-CのBlocksでカリー化関数と部分適用
すごいH本を少しずつ読み進めているんだけど、なかなか進まない。iOS6の新APIの調査の方に時間を取られています*1。
5章くらいまで読んでるところだが、カリー化の説明がサラッと終わって消化不良なので、Objective-C*2で書いてみた。
multiplyThree(2)(3)(4)
で、2,3,4を引数に取り、2*3*4を返します。
typedef int (^multiplyBlk)(int); typedef multiplyBlk (^multiplyTwoBlk)(int); typedef multiplyTwoBlk (^multiplyThreeBlk)(int); multiplyThreeBlk multiplyThree = ^multiplyTwoBlk(int x) { multiplyTwoBlk multiplyTwo = ^multiplyBlk(int y){ multiplyBlk multiply = ^(int z){ return x * y * z; }; return multiply; }; return multiplyTwo; }; NSLog(@"%d", multiplyThree(2)(3)(4)); // => 24
部分適用もできます。
multiplyTwoBlk multiplyTwoBy5 = multiplyThree(5); NSLog(@"%d", multiplyTwoBy5(6)(7)); // => 210
確かHaskellだとこんな感じ
multiplyThree :: Num a => a -> a -> a multiplyThree x y z = x * y * z
Haskellなら2行で済むものを、わざわざObjective-Cで書く意味？ないよそんなもん。
Haskellの本を買ってみた
amazon:すごいHaskellたのしく学ぼう！
とりあえずfizzbuzzを書いてみる。
-- ghci Prelude> [if x `mod` 15 == 0 then "fizzbuzz" else if x `mod` 3 == 0 then "fizz" else if x `mod` 5 == 0 then "buzz" else show x | x <- [1..100]] -- output ["1","2","fizz","4","buzz","fizz","7","8","fizz","buzz","11","fizz","13","14","fizzbuzz","16","17","fizz","19","buzz","fizz","22","23","fizz","buzz","26","fizz","28","29","fizzbuzz","31","32","fizz","34","buzz","fizz","37","38","fizz","buzz","41","fizz","43","44","fizzbuzz","46","47","fizz","49","buzz","fizz","52","53","fizz","buzz","56","fizz","58","59","fizzbuzz","61","62","fizz","64","buzz","fizz","67","68","fizz","buzz","71","fizz","73","74","fizzbuzz","76","77","fizz","79","buzz","fizz","82","83","fizz","buzz","86","fizz","88","89","fizzbuzz","91","92","fizz","94","buzz","fizz","97","98","fizz","buzz"]
まだ20ページくらいしか読んでないので、まだまだ手続き脳です。
