Haskellで何か作りたい。でも何か作れるほどHaskellわからない。
と思ってたらBitTorrentクライアントのチュートリアルっぽいものを見つけたので、せっかくだし作ってみようという話です。

以前の記事で作っていたBencodeのパース部分をとりあえず書いてみました。

{-# LANGUAGE OverloadedStrings #-}

module Bencode where

import Control.Monad
import Control.Applicative
import Data.Attoparsec.ByteString (Parser)
import qualified Data.Attoparsec.ByteString.Char8 as B
import Data.ByteString

data BValue = String ByteString
            | Number Integer
            | List [BValue]
            | Dictionary [(ByteString, BValue)]
            deriving (Show)

string :: Parser BValue
string = do
    n <- B.decimal
    void $ B.char ':'
    String <$> B.take n

number :: Parser BValue
number = Number <$> (B.char 'i' *> B.signed B.decimal <* B.char 'e')

list :: Parser BValue
list = List <$> (B.char 'l' *> B.many' value  <* B.char 'e')

dictionary :: Parser BValue
dictionary = do
    void $ B.char 'd'
    pairs <- B.many' ((,) <$> string <*> value)
    void $ B.char 'e'
    return $ Dictionary $ fixPair <$> pairs
    where fixPair (String s, v) = (s, v)

value :: Parser BValue
value = string <|> number <|> list <|> dictionary

実行してみます。

ghci> :set -XOverloadedStrings
ghci> B.parseOnly value "d8:announce42:http://tracker.archlinux.org:6969/announce13:creation datei1438414567e4:infod6:lengthi688914432e4:name29:archlinux-2015.08.01-dual.iso12:piece lengthi524288eee"
Right (Dictionary [("announce",String "http://tracker.archlinux.org:6969/announce"),("creation date",Number 1438414567),("info",Dictionary [("length",Number 688914432),("name",String "archlinux-2015.08.01-dual.iso"),("piece length",Number 524288)])])

Attoparsecにも少しずつ慣れてきた気もします。
とりあえずここまで。

2016-10-21

Attoparsecのメモ

blog.chaps.io

上のサイトを見ながら、Bencodeのパースをするコードを書いていたら、そもそもParsecやAttoparsecというパースライブラリについて全然わからなかったので、メモがてら記録をしておきます。
ParsecよりもAttoparsecの方が早いと聞いたのと、上のサイトはAttoparsecを使ってるのもあって、こっちを触ってみます。

http://hackage.haskell.org/package/attoparsec-0.13.1.0/docs/Data-Attoparsec-ByteString-Char8.html

パース実行するときに使う関数がparseです。

parse :: Parser a -> ByteString -> Result a

パーサーとパース文字列を入れると結果が返ってくる。わかりやすいです。

日付のパーサーだったらこんな感じで書けそうですね。

{-# LANGUAGE OverloadedStrings #-}

import Data.Attoparsec.ByteString
import qualified Data.Attoparsec.ByteString.Char8 as B
import Data.ByteString

parseDate :: Parser [Integer]
parseDate = do
    y <- B.decimal
    B.char '/'
    m <- B.decimal
    B.char '/'
    d <- B.decimal
    return [y, m, d]

ghciを起動して読み込んでみます。

*Data.Attoparsec.ByteString B> parse parseDate "2016/10/25"
Partial _

あれ？

Partial (i -> IResult i r)
Supply this continuation with more input so that the parser can resume. To indicate that no more input is available, pass an empty string to the continuation.

どうやらパーサーが途中で止まっているかららしい。
”2016/10/25”という文字列だと、最後が数字なので、「次の数字はまだかー？」ってパーサーが待っているってことなんでしょうか。

*Data.Attoparsec.ByteString B> parse parseDate "2016/10/25x"
Done "x" [2016,10,25]

入力文字列の最後に数字以外の文字を入れたらパーサーが止まったらしく、終了しました。

1回だけパースを実行したいときには、parseOnlyという関数があるみたいです。

*Data.Attoparsec.ByteString B> parseOnly parseDate "2016/10/25"
Right [2016,10,25]

Bencodeのパースをするコードはもうちょっと複雑そうですね。
それはまた今度で。

2016-04-13

ラムダ計算の練習

今日は型システム入門第5章のラムダ計算でのプログラミングを読んでいます。
その読書メモです。

ラムダ式の項の種類

x (変数)
λx. t (ラムダ抽象)
t t (関数適用)

変数のスコープ
f = λx. x (λx. x)

上記ラムダ式の赤文字のxと青文字のxは別物。
fにaを適用すると、f a = (λx. x (λx. x)) a = a (λx. x)となる。

β簡約
(λx. u) vのような形の項があったとき、uの中に出現するすべてのxをvで置き換える操作のこと。
この式をβ簡約すると、(λx. u) v → u[x := v]となる。（ラムダ式uに出現するxをvに置き換えてる）
上式のuがu=x y zだった場合、上記操作を行うと、(λx. x y z) v → v y zのようになる。

ラムダ抽象に対して関数適用を行った場合、こんな感じで簡略化できますよーということかな？
ラムダ式を使ってて無意識に行っていたことをちゃんと文章にしたらこうなるんですね。

カリー化
ラムダ式のラムダ抽象は、複数の引数を取ることができない。
複数引数を取る関数を使いたい場合は、高階関数を使って同じような関数を作ることができる。
複数の引数を取る関数を高階関数に変換することをカリー化という。

x,yの2つの変数を取る関数f(x, y) = x+yを考える。
ラムダ式では、
f = λx. λy. x+yという風に書く。

f に2と3を適用してみると、

f 2 3
= (λx. λy. x+y) 2 3
= (λy. 2+y) 3
= 2+3

となる。

(λx. λy. x) 2 3 → (λy. 2+y) 3が、λx. λy. x+y → (λy. x+y) [x := 2]のβ簡約。
(λy. 2+y) 3 → 2+3が、(λy. x+y) [x := 2] → (x+y) [x := 2][y := 3]のβ簡約。

複数引数を取る関数と同等の働きをしていることがわかった。

とりあえずここまでです。
次は明日あたりに読みます。

2016-04-12

型無し算術式の実装

型システム入門の第4章　算術式の実装がOCamlで書かれていたので、勉強がてらHaskellで書いてみました。

import Data.Maybe (fromJust)

data Term = T_TRUE | T_FALSE | T_ZERO | T_SUCC Term | T_PRED Term | T_ISZERO Term | T_IF Term Term Term deriving (Eq, Show)

eval :: Term -> Maybe Term
eval t | isv t = Just t
       | otherwise = step t >>= eval

step :: Term -> Maybe Term
step (T_IF T_TRUE t2 t3) = Just t2
step (T_IF T_FALSE t2 t3) = Just t3
step (T_IF t1 t2 t3) = if t1' /= Nothing then Just (T_IF (fromJust t1') t2 t3) else Nothing where t1' = step t1
step (T_SUCC t1) = if t1' /= Nothing then Just (T_SUCC (fromJust t1')) else Nothing where t1' = step t1
step (T_PRED T_ZERO) = Just T_ZERO
step (T_PRED (T_SUCC t1)) | isn t1 = Just t1
step (T_PRED t1) = if t1' /= Nothing then Just (T_PRED (fromJust t1')) else Nothing where t1' = step t1
step (T_ISZERO T_ZERO) = Just T_TRUE
step (T_ISZERO (T_SUCC t1)) | isn t1 = Just T_FALSE
step (T_ISZERO t1) = if t1' /= Nothing then Just (T_ISZERO (fromJust t1')) else Nothing where t1' = step t1
step _ = Nothing

isn :: Term -> Bool
isn T_ZERO = True
isn (T_SUCC x) = isn x
isn _ = False

isv :: Term -> Bool
isv T_TRUE = True
isv T_FALSE = True
isv x | isn x = True
isv _ = False

OCamlみたいにパターンマッチ使ってます。
実行時エラーを考慮して、計算結果にはMaybeモナドを使っています。

評価関数evalを使ってみると、こんな感じになります。

*Main> eval $ T_IF (T_ISZERO T_ZERO) T_FALSE T_ZERO
Just T_FALSE

*Main> eval $ T_IF (T_ISZERO (T_SUCC T_ZERO)) (T_SUCC $ T_SUCC $ T_SUCC $ T_ZERO) T_ZERO
Just T_ZERO

*Main> eval $ T_IF T_ZERO T_TRUE T_FALSE
Nothing

2016-04-11

型システム入門を読む

久しぶりに書きます。

estore.ohmsha.co.jp

型システム入門という本を買ってしまったので、読んで勉強します。
私は型に対する理解が未だに曖昧なので、これを読んで少しでも理解を深められたらと思っています。

3章の型無し算術式までは読んでみましたが、集合やら関係やらの知識が不足していることもあって難航しています。
とりあえず4章を読んでみて、必要があれば読み直すことにします。

2015-12-10

階乗でつまづくの巻

paiza.jp

先日からHaskellで挑戦してました。
一通りの問題を解いたのですが、彼女の水着を手に入れるための問題が全然通らなくて、あれれ？＞＜状態です。

問題
「N!（Nの階乗）から、最下位桁から続く0を全て除いた値の下位9桁を出力せよ。」

条件
1 <= N <= 1000000
最下位桁から続く0を全て除いた値の下位9桁の最上位桁から0が続いている場合、その0は全て消去する。

詳しくはサイトから見て頂けると。。。

現状のコードはこちらです。

import Control.Applicative
import Data.List

fracB :: Integer -> Integer
fracB 0 = 1
fracB n = del0 (n * fracB (n-1)) `mod` 1000000000 + 1000000000
    where del0 x = if x `mod` 10 == 0 then del0 (x `div` 10) else x

main = do
    n <- (read::String->Integer) <$> getLine
    print $ cut9 $ fracB n
        where cut9 = read . reverse . take 9 . reverse . show :: Integer -> Integer

まともに計算すると桁がすごいことになったので、積ごとに下位桁に出てきた0を消すようにしました。（del0関数）
下位9桁の情報が分かればいいので、9桁を越えたら上の桁は消すようにしました。

いくらかのテストケースは通るのですが、全部は通らず。ぐぬぬ...。

このブログを書きながら、上位桁を消すときに情報漏れが発生しているのかなぁと思いました。
いろいろ試してみて、通ったらまた更新してみます。。。

2015-08-21

動的計画法の勉強

動的計画法がよく分からないので、お勉強しました。
Haskellで書いてます。

この問題を解いてみました。
No.45 回転寿司 - yukicoder

コードです。

main = do
    _ <- getLine
    sushi <- getLine
    let sushiList = map read (words sushi) :: [Int]
    let dpt = dp sushiList
    putStrLn $ show $ head dpt

-- DP table create
dp :: [Int] -> [Int]
dp dt = foldl (\(d1:d2:dx) x -> (max d1 (d2 + x)):d1:d2:dx) [0,0] dt

動的計画法を使って解きました。
正解のようですけど、これ本当にあってるのか不安になりました。

漸化式がこれでいいのか確かめてみます。

===============================================

X_n : n番目のお寿司
M_n : n番目のお寿司を取った、もしくは取らなかったときの、最大累計美味しさポイント

まず、M_nを考えてみます。
X_nを取る、取らないの2パターンが考えられます。

取るとき : 1個前のお寿司は取れない。
取らないとき : 1個前のお寿司を取っても良い。

まず、X_nを取ったときのパターンを考えます。
X_nを取ったときは、X_n-1を取っていません。
ということは、1個前のお寿司が流れてきたときには美味しさポイントが増えてないということです。
つまり、M_n-2 >= M_n-1
ということは、X_nを取ったときの M_nは、X_n + M_n-2と言えそうですね。

次に、X_nを取らなかったときのパターンを考えます。
お寿司を取らなかったということは、1個前のお寿司が流れてきたときと美味しさポイントが変わっていないということです。
なので、X_nを取らなかったときのM_nは、X_n-1と言えそうですね。

ここで、
M_n = X_n + M_n-2
M_n = X_n-1
の、2パターンの式が出ました。
求めたいのは、最大のM_nなので、

M_n = max(X_n + M_n-2, M_n-1)

ということになります。

===============================================

こんな感じでしょうか。
正確に証明できていないような気がします。
あと、Haskellの書き方ももっと良い方法がありそうな気がします。

コメントなどで指摘してもらえると、嬉しいです。

プログラミング勉強日記

勉強したことを書きます。Haskellとか。

HaskellでBitTorrentクライアントを作りたい