Hatena::ブログ(Diary)

しんちゃんの日記

2017-06-25 Haskellはライブラリ化進めればLLより汎用性高いコードを短く書ける

自作ライブラリとそれを使った成果物。
LLだとここまでライブラリ化するとreverse使わない場面でもメモリに溜め込みまくったり、それを解消するためにイテレータ作りまくったりする必要があるんじゃなかろうか。
それでなくとも副作用と純粋部分が分かれてない処理があるとライブラリ化しにくい。
rpコマンドはreplaceとかrepと付けたかったけど、sudo apt installしてないパッケージに同名のコマンドが複数あるらしいので。
rpコマンド、なるべくユニークな文字列にしないと危険だけど、関数名や引数の名前や順序変えた時に複数ファイル・複数箇所を修正するので地味に大活躍…。

Myfunc.hs(自作ライブラリ)
module Myfunc where

import Data.List
import Text.Printf

consnum::(Int,String) -> String
consnum (i,xs) = printf "%4d:%s" i xs

fline f = unlines.f.lines

fnumbering f = fline ((map consnum).(zip [1..]).f)

redstr::String -> String
redstr [] = []
redstr w = printf "\ESC[1m\ESC[31m%s\ESC[39m\ESC[0m" w

bluestr::String -> String
bluestr [] = []
bluestr w = printf "\ESC[34m%s\ESC[39m" w

grep w = fline (filter (isInfixOf w))

replace _ _ [] = []
replace [] _ cs = cs
replace w nw cs | w == take (length w) cs =
                        nw ++ replace w nw (drop (length w) cs)
replace w nw (c:cs) = c:replace w nw cs

putfc (f,c) = printf "%s\n%s" f c

writefc (f,c) = writeFile f c

mfptn fs f ofs output = mapM readFile fs >>=
                        return.(zip ofs).map f >>=
                        mapM_ output

mfput f fs = mfptn fs f (map bluestr fs) putfc

mfwrite f fs = let tfs = map (++ ".temp") fs in
               mfptn fs f tfs  writefc >>
               mfptn tfs id fs writefc

number.hs(ナンバリングコマンド)
import System.Environment
import Myfunc

main = getArgs >>= mfput (fnumbering id)

revnumber.hs(行番号付き行の逆順表示コマンド)
import System.Environment
import Myfunc

main = getArgs >>= mfput (fnumbering reverse)

mygrep.hs(検索文字列のある行を表示するコマンド。見つかった文字列を強調赤字で表示)
import System.Environment
import Myfunc

main = getArgs >>= \(w:fs) ->
       mfput ((replace w (redstr w)).(grep w).fnumbering id) fs

rp.hs(文字列置換コマンド)
import System.Environment
import Myfunc

main = getArgs >>= \(w:nw:fs) -> mfwrite (replace w nw) fs

2017-06-19 巨大なファイルを逆順で表示するCプログラム

ネットで1000万行のファイルを読み込ませて逆順にしたいとか言うのを(perlで)みたので、Cで1500万行近くまで対応してみた。


やり方としては一回EOFまでfputs回して、ftellで位置情報を配列に記録。
配列の逆から位置情報読み込んでfseekで移動を繰り返す。
記録時間が最初かかるけど、配列の大きさからビビっていたほどはメモリも消費しない。
(1400万行3.1GBの文字ファイルに対し、4GBメモリの0.6%)

#include<stdio.h>
#include<stdlib.h>

int main(int argc, char *argv[])
{
    for(int i = 1; i < argc; i++)
    {
        FILE *fp;

        if((fp = fopen(argv[i],"r")))
        {
            const int BUF = 1024 * 4;
            char s[BUF];
            long *fpos;
            int k = 0;
            
            puts(argv[i]);
            fpos = malloc(sizeof(long)*15000000);
            if (fpos == NULL) exit(0);
            fpos[++k] = ftell(fp);
            while((fgets(s,BUF - 1, fp)))
            {
                fpos[++k] = ftell(fp);
            }
            int j = 1;
            fseek(fp,fpos[--k],SEEK_SET);
            while(fgets(s,BUF - 1,fp)) 
            {
                if(k > 0)
                {
                    printf("%4d:%s", j++, s);
                    fseek(fp,fpos[--k],SEEK_SET);
                }
            }
            free(fpos);
            fclose(fp);
        }
        else
        {
            printf("ファイル[%s]がありません\n",argv[i]);
            return -1;
        }
    }
    return 0;
}

2016-06-19

自分なりの宣言的プログラミングの定義

関数型言語や論理型言語(Prolog)は宣言的にプログラミングが出来ると入門書には書いてることがあります。
一方で、Javaの本でも宣言的なコードと書かれたものがあります。
どうもメソッド呼び出しのみが並ぶようなコードっぽい。

となると、ifやfor等の制御構造が無ければ宣言的と言う事なのかな?
まあ、手続き型言語関数オブジェクト指向も、もとは抽象的に扱うための物ですしね。
宣言的であるのと、参照透明な事は関係ないと考えればしっくりきます。
昔、2chで型がある言語で書く人はクラスをよく書くけど、型のない言語で書く人はクラスをあまり書かないとか見かけましたが、ある意味ではクラスを書かなくて済むくらいになるのが手続き型言語抽象化の理想ではないかと。
手続き的な処理は一切書かなくて良くて、全てメソッド関数の呼び出しだけで完結できるようになったら、関数型言語と同じくらいの抽象度になっているのかもしれません。

そう言えば、次期JavaScriptが末尾再帰最適化出来るようになるそうですね。
理屈の上では手続き型言語だって出来ると思ってましたので、他の手続き型言語にも採用されていくと思います。
しかし、Haskellはいつの間にか普通の(単純な)再帰も(恐らく内部で末尾再帰に変換して)ループになるようになってました。
これは地味にうれしい。
これも、いずれは手続き型言語に採用されていくように思いますが、もう少し先でしょう。

C#型推論もまだまだですね。
そして、あれ以上の推論は手続き型では無理な気はしますね。
手続き型で関数型言語並みの抽象度になるのは結局LLやsmalltalkの様な型の無い言語だけのように思います。

だったら、型があって抽象度の高いHaskellが(ry

2016-06-15

Haskellで九九

手続き型言語では、オブジェクト指向全盛になった今もついループで書いちゃう九九。
じゃあ、ループじゃない書き方ってどんなだろう?と思ったので書いてみた。

import Text.Printf

kuku =putStr $ concat [nineLines x y | x <- [1..9], y <- [1..9]]
    where
        nineLines :: Int -> Int -> String
        nineLines x 9= printf "%2d\n" (x * 9)
        nineLines x y= printf "%2d " (x * y)

うん。普通にLLでも書けますね。
でも、何故か書かない。
そんなコードでした。

HaskellのIOモナドは副作用は有るかも知れないけど、参照透明性は失われてないと思う

すごいH本を読み終えての感想。
IOモナド、あるいはアクションと呼ばれるものは、Haskellの中ではリストやMybeと同列。
ただIO型はモナドインスタンスにしかなってないだけ。
(まあEqもOrdも出来ないからインスタンスになれないよね…)
なのでリストの中にputStrとかを入れたりできる。

IO型の関数モナド逐次処理をエミュレートしながらも、遅延評価のおかげで参照透明性は失われてないと思う。
エミュレートは所詮エミュレートだと言う事。

例えば、
文字を入力して出力するプログラム

main = do
    x <- getContents
    putStr x

一見、putStr xから先に実行すると破綻しそうだが、遅延評価なのでputStrが必要になったらgetContentsを呼びに行く。
だから入力→出力の順で実行される。
(というか、実際そんな順序で実行されてる)
もちろん、コード通りにgetContentsから実行されれば普通の逐次処理。
ちなみに、ループが書かれてないけどこれは入力と出力を永遠に続ける無限ループします。
というのは、ファイルの終端まで入力してから出力するはずが、標準入力にはファイルの終端が無いため、遅延評価により一行毎(入力確定毎)に出力を繰り返します。
作ったプログラムリダイレクトでファイルを入力するようにすると、期待通りファイル内容を表示して終了します。

次に、入力だけのプログラム

main = do
     x <- getContents

これはdo表記を使わないとこうなる。

main = getContents >>= \x -> x

つまり、xに値が入ってから入力が開始されるのはおかしい。
では、Haskellはどう解決するのか?
遅延評価は求められない限り何もしない。
つまり、出力しない値は無いも同じなので、入力も何もせずに終了する。
ほらね?
参照透明性は失われてないでしょ?

すごいH本のファンクターまで読んだときに思ったのは、IO型はプログラム型とかアプリ型とか呼びたくなるって事。
リストやMybeとかと同じ値を入れる型だけど、すごいH本で言う文章付き型(複数の値を入れる型や、失敗の可能性のある型)とすれば、プログラムとして動作する型とでも言おうか…。
型としてのプログラム型は同じ形の入れ物。(だから、Haskellの文法上副作用はない)
プログラム型がプログラムとして実行されると副作用を伴う的な。
済みません。
まだ頭の中で整理できてない。

2016-04-18

熊本へ支援物資届けた時に感じたことと、ボランティア心得的なまとめ

まさかまたはてなダイアリーを使う日が来ようとはね。。。
熊本へ支援物資届けた後、つらつらとツイートしたのをここにまとめます。