Haskellの勉強をしていたら、Elixirのパイプライン演算子がF#由来であることを知った

Elixirというプログラミング言語に、パイプラインマクロ演算子というのがあり、面白いなーと思っていた。お前らElixirとか知らないだろうから、これがどんなものか後で書くとして、Haskellの勉強をしていたら同等のものを実装している記事をみつけ、どうもこれはF#由来であることを知った。


さて、くだらない例だけど、数のリストに何か(map)して条件を満たすものを抜き出して(filter)、最後に足す(fold)みたいなことって、Haskellでは普通たとえば次のように書く（と思う）

Prelude>  sum . filter even . map (+1) $ [1..10]
30

Haskellなんて知らない人もいると思うので、ほぼ同等のコードをPerlで書くとこうなる

use strict;
use warnings;
use List::Util qw/sum/;

my $ans = sum grep { $_ % 2 == 0 } map { $_ + 1 } (1 .. 10);
print( $ans );

細かな文法の違いはあれ、やってることは同じだ。
Rubyの人ならこう書きたいかもしれない

irb> (1..10).map{|x| x + 1 }.select{|n| n.even? }.reduce(0){|a, b| a + b }
=> 30

どちらがいいということはないのだけど、行う処理の内容によってはRubyのような順番で書いたほうがわかりやすいこともある。（Unixのコマンドをパイプラインでつないでいくことを思い出してほしい）
F#にはパイプライン演算子 |> という、そういうことを実現する演算子があるらしい。Haskellではそれを実現する演算子（というかただの関数）を簡単に書くことができ、次のように書く

-- |pipeline operator
-- >>> sum . filter even . map (+1) $ [1..10]
-- 30
--
-- >>> [1 .. 10] |> map (+1) |> filter even |> sum
-- 30
infixl 0 |>
(|>) :: a -> (a -> b) -> b
x |> f = f x

Elixirのパイプラインは昔はマクロで実装されていて名前も /> だったが、最近のリリース(0.7.2)で組み込みの演算子になって名前も |> になったようだ。

iex(4)> [1,2,3,4] |> Enum.map(&1 + 2) |> Enum.filter(fn(x) -> rem(x, 2) == 0 end) |> List.foldl(0, &1 + &2)
10

なおElixirの関数はHaskellみたいにカリー化されていたりはしないので、普通はこんなもの作れない。結局組み込み演算子になったが、もしこういうのをユーザが作ろうとしたらマクロ（Exlirのマクロは抽象構文木を操作する本物のマクロだ）でも使うしかないと思う。ということは本物のマクロがない言語だと後からこういうのを作るのは難しい。


さて、これだけだと id:kazu-yamamoto さんの記事を読めばいいっていう話でつまらないので、F#の関数合成演算子 >> と同等のものをHaskellで作ってみた。いや、作ってみたといってもこれも糞簡単なのだが。
Haskellにはもちろん関数合成演算子 . があるし上でも使っているが、F#のそれとは逆順である。 |> で値を渡していくのは楽しいが、引数を最初に渡さなければいけないので、結果として関数が欲しい時はラムダ式にするしかない。

Prelude> (\s -> s |> map (+1) |> filter even |> sum) [1 .. 10]
30

でもたぶんHaskellだと、そのような関数を作り出したいこともあるだろう。逆順の関数合成演算子 |>> は以下。

-- |pipelined compose operator
-- >>> (map (+1) |>> filter even |>> sum |>> show |>> putStr) [1 .. 10]
-- 30
--
-- >>> :m + Data.List
-- >>> ( words |>> sort |>> group |>> map (\ls -> (head ls, length ls)) ) "ab a b a a b"
-- [("a",3),("ab",1),("b",2)]
infixl 0 |>>
(|>>) :: (a -> b) -> (b -> c) -> a -> c
g |>> f = f . g


あ、ソースコードはgithubにあげた。doctest形式の使用例兼単体テストもある。

やはりお前らはSICPを読むといい

この記事はVOYAGE GROUP Advent Calendar の12/24分です
なんか推敲が間に合わず、12/24に間に合いませんでしたが、今更だします。ごめんなさい。


SICP（計算機プログラムの構造と解釈）と言う本をご存知ですか？私はこのSICPという本が大好きで、社内でも何度も読書会を催しています。なぜ読書会をするかというと、一人で読みきるのは辛い（人もいる）ためです。
この記事では何がそんなに良いのかという説明をします。


そもそもこの本は、MITの6.001という計算機科学講義の教科書としてデザインされ、実際に使われていたものだそうです（今は別な本が採用されている）。

同様の初歩的な計算機科学の教科書の中でこの本が特異だと私が感じるのは、おまじないやお約束を可能な限り廃して、ごく少数の根本的な動作原理のみを仮定して、変数とは何か、関数とは何か、プログラミングするという行為は何かを説明しようとしている点です。

いわゆる有名な Hello World のC版を掲載します。これだけのプログラムの中にいくつのおまじないが含まれるでしょうか。

#include<stdio.h>   /* Q.これは何？ A.おまじない */

main()  /* Q. これは何？ A.おまじない */
{
    printf("hello world\n");    /* Q. printf ( " \n ) ; はそれぞれ何？ A. おまじない */
}

ああ、確かにLLだともっと短くできます。しかしここで問題にしているのはおまじないの少なさで、putsって何？という初学者の至極もっともな問に真剣に答えようとすると割りと面倒なのではないでしょうか。

puts "hello world"  # putsは関数？メソッド？メッセージ？基本手続き？標準ライブラリ？

あるいは、今はもう違和感を忘れてしまっただろうけど、次の式（言語によっては文）を見て下さい。

i = i + 1

i = i + 1 だって？等式が成り立ってないじゃないか！

あなたもきっと昔はこれに違和感を覚えたはずなのです。今や違和感を忘れてしまったあなたは、これに違和感を持つ初学者にどう説明するといいのでしょうか？


なぜこれらの説明が困難かというと、それはこれが本当は難しいことをしているからです。
本当はIOは難しいし、副作用も難しいのです。

じゃあSICPではどう説明しているかというと、IOに関する説明はほとんどしていないか最小限で、副作用に関しては最初は説明しません。副作用がない最小限のルールだけで記述できる動作モデルを最初は提示します。しばらくの間、その動作モデルの中でできる色々な面白いことを説明します。そしてしかるべき後に副作用をも説明できる完全なルールを提示しています。


「動作モデル」と言いました。あるいはその前に「動作原理」と言いました。SICPはひたすら動作モデルの説明をしているのだという見方をすることもできます。
その見方の上では、SICPの章立てを以下のように見ることもできます（「手続き」という用語は、他の言語でいう「関数」と思えばよいです。プログラム言語における「関数」は厳密には数学における「関数」ではないため、SICPでは謙虚に「手続き」と呼んでいるものと思います）。

  • 1章 手続き作用の置き換えモデルと手続き抽象
  • 2章 データ抽象
  • 3章 手続き作用の環境モデルと副作用
  • 4章 動作モデルを実際にプログラムで実装する＝評価器（eval手続き、またはインタープリタ）の実装
  • 5章 評価器を何かの機械語に変換する＝翻訳器（コンパイラ）の実装

この本を読むと何がいいのか。それはプログラムの動作モデルが身につくことです。おまじないや、スニペットのコピペや、経験則（＝よく分からないがこう書くとこう動く）ではなく、明確な原理に基づいて、明確な意思と意図をもってプログラムを記述し、読み、抽象を構築することができるようになります。

完全な初学者が読んでもまあいいのかもしれませんが、職業プログラマで一応のプログラムの書き方は分かるが、本格的な計算機科学の教育を受けたことがなく、基礎に不安があるような方が、一歩先に進むための本としてもお勧めです。
興味を持たれた方は、正月休みにでも、読んでみるといいのではないでしょうか。

構造体の暗黙のコンストラクタ？

C++

どうしても高速化したい処理があって久々にC++を書いています。
が、書いていてあれ？と思うことがあったので記事を書いてみます。

サンプルコードは以下のようなものです。

#include<iostream>
#include<string>
#include<map>

struct point { int x; int y; };

void disp(const point& pt) {
    std::cout << "(" << pt.x << ", " << pt.y << ")" << std::endl;
}

int main(){
    //garbage value
    point pt1;
    disp(pt1);

    // (0, 0)
    std::map<std::string, point> m;
    disp(m["hoge"]);

    // (0, 0) implicit constructor? 
    point pt2 = point();
    disp(pt2);

    // (0, 0) initialize 
    point pt3 = {};
    disp(pt3);

    return 0;
}

http://codepad.org/8qhpf4hW

    //garbage value
    point pt1;
    disp(pt1);

これがゴミを表示するのはCの感覚で言えば納得です。
ところが

    // (0, 0)
    std::map<std::string, point> m;
    disp(m["hoge"]);

なんとこれは "(0, 0)" と表示されるのでした。
std::map の operator[] は、キーに対応するエントリが存在しない場合にはデフォルトコンストラクタでオブジェクトを作る的な理解をしていましたが、pt1のケースと挙動が異なるわけです。
えっ？と思って使っているコンパイラのSTLのmapのソースなどを読んでみたり色々試していると、どうも

    // (0, 0) implicit constructor? 
    point pt2 = point();
    disp(pt2);

このような書き方では "(0, 0)"に初期化されるようなのでした。
C++の構造体はpublicがデフォルトである以外はclassと同じというのは知っています。
と言うことはC的な記述で構造体を宣言した場合は、コンパイラが暗黙のコンストラクタやらコピーコンストラクタなどを作ったりするのだろうという思い込んでいたのですが、しかし pt1 の書き方と pt2 の書き方は等価であると思っていました。
まあただ、以下のような書き方(これもpt1やpt2と等価でデフォルトコンストラクタが呼ばれると思っていました)はコンパイルエラーになったので何か勘違いしているのかもしれません。

    // compile error 
    point pt4();
    disp(pt4);

普通であれば class にしてコンストラクタも明示的に与えるべきなのでしょうが、高速化が目的なので可能でありかつ仕様に則った挙動であるならば余分なことを書かずに済ませたいのですが、いやはや・・・
プログラミング言語C++をざっと眺めただけでは、この挙動を正当化する記述は見つけられませんでした。となるとC++の仕様書を読むべきなのでしょう。あんまり読みたくないし、読んでも処理系が仕様に則っているかどうかも定かではないという。。

妥当性とは仕様の所作 - SQLインジェクション対策とバリデーション


繰り返しになりますが、妥当性検証は仕様の問題であってセキュリティ対策ではありません。

バリデーションは仕様の問題であってセキュリティ対策ではないとはどういうことか説明します。SQLインジェクションの対策は、1. SQLを文字列結合で作らない 2. プレースホルダを使う です。バリデーションは関係ありません。

簡単な例

Webアプリケーションで郵便番号を指定するフォームを考えましょう。
日本の郵便番号を指定するフォームの設計でよく見るものは大きく分けて2通りあり、上3桁と下4桁を別々に入力させるものと、1つのフォームにまとめて入力させるものです。住所から補完させる設計もありえますがここではおいておきます。



<input type="text" name="postal_code_1"> - 

<input type="text" name="postal_code_2">



<input type="text" name="postal_code"> 例：100-0001

どちらを選んでもよいのですが、選んだ設計によって仕様が変わることに注意してください。
クエリパラメタ postal_code_1 を受け取ったサーバは数値のみを妥当な入力として受け入れる仕様となるでしょう。その際にいわゆる半角数字のみを受け入れるのか、いわゆる全角数字が入力されたら適切に変換してあげるのかを決める必要があります。
postal_codeの場合は数値のみ7桁の入力を受け入れるか、ハイフンを必須とするか、いわゆる全角のハイフンはどうかなどをさらに意思決定する必要があります。

ここでは以下の一連の意思決定をし、それを共有して仕様としたとします。

  • クエリパラメタ postal_code_1 は郵便番号上3桁の数値文字列を受け取る
  • クエリパラメタ postal_code_2 は郵便番号上4桁の数値文字列を受け取る
  • いわゆる全角文字の入力については、いわゆる全角数値がUTF8で表現されている場合のみ受け入れた上でサーバ側でいわゆる半角数値に変換する
  • 入力が数値のみで構成されているが必要な桁数に満たない場合は、「7桁の郵便番号を入力してください」というメッセージを表示して再入力を促す
  • それ以外の入力については、「郵便番号を入力してください」というメッセージを表示して再入力を促す

ここで行うバリデーションは、postal_code_1/postal_code_2 それぞれが「数値」のみで構成されているかどうか、必要な桁数であるかどうか、になります。
ここまでの仕様をさだめないとバリデーション（妥当性検証）は定義できないことに注意してください。何をもって妥当とするかは仕様が定めるものであり、従って仕様がなければ妥当性を論じることはできません。また、postal_codeに7桁分入力される場合は全く異なるバリデーションを行うことになります。

バリデーションがセキュリティ対策とは異なる具体例

マイクロブログサービスを作るとしましょう。

  • ユーザのつぶやきは最大140文字（バイト数ではなく文字数）
  • 空のつぶやきは受けつけない
  • 妥当なUTF8エンコーディング文字列のみを受けつける
  • 140文字を超えるつぶやきはメッセージを表示して再入力を促す

この仕様のもとでできるバリデーションは

  • つぶやきのエンコーディングが妥当かどうか
  • 文字数が1文字以上140文字以下であるかどうか

だけです。「"K&R" from 」のようなつぶやきは仕様上妥当な入力ですので受け入れる必要があります。
この入力にはSQLやHTMLとして特別な意味を持つ文字が含まれていますが、そもそもRDBMSとのやり取りで適切にプレースホルダを使用していたり、HTMLとして出力する直前にHTMLとして特別な意味を持つ文字を適切にエスケープしていれば気にする必要はありません。
ここで、「危険ｗｗｗな文字列を削除すればいいんじゃね？ｗｗｗ俺天才ｗｗｗｗｗ」として「KR from OReilly」のようにしてしまう愚行など、何が正しいか理解しないで不適切な対症療法をとることを専門用語で「サニタイズ脳」と言います。

バリデーションは仕様の問題であってセキュリティ対策ではないというのはこういう意味です。繰り返しになりますが、SQLインジェクションの対策は、1. SQLを文字列結合で作らない 2. プレースホルダを使う です。バリデーションは関係ありません。
文字列結合でSQLを構築するなど不適切な取り扱いをしている場合は、上記のような仕様ではバリデーションを行なってもおかしなSQLになることでしょう。

#tqrk03 で発表した内容がアレだったので、無限ストリームをrubyでやった

東急Ruby会議(#tqrk03)に遊びに行ったら、@tadasyの罠にハメられて無意味に3分LTすることになった。
なんの準備もしてなかったので、空気を読まずに前の記事に書いたHaskellがすげえっていう話をすることにした。
だってRubyわかんねーんだもん。
んで、みんな酒が入った勢いで笑ってたが何一つ意味分からなかったと思われるので、無限ストリームのやつをRubyに移植した。私はRubyまったくわからないので、なんかおかしな書き方だったら教えてほしい。
プログラムだけ書いて力尽きたので、解説が必要な人はSICPを読んでほしい。

class Stream
	def initialize(car, &cdr)
		@car = car
		@cdr = cdr
	end

	def car
		@car
	end

	def cdr
		@cdr.call
	end

	def take(n)
		(n == 0) ? [] : (cdr.nil?) ? [@car] : cdr.take(n-1).unshift(@car)
	end

	def ref(n)
		(n == 0) ? @car : cdr.nil? ? nil : cdr.ref(n-1)
	end

	def map(&f)
		Stream.new(f.call(@car)) { cdr.map(&f) }
	end
end

class << Stream
	def zipWith(s1, s2, &f)
		car = f.call(s1.car, s2.car)
		new(car) { zipWith(s1.cdr, s2.cdr, &f) }
	end

	def repeat(x)
		new(x) { repeat(x) }
	end

	def integerStartinFrom(n)
		new(n) { integerStartinFrom(n+1) }
	end

	def integer
		integerStartinFrom(1)
	end

	def add(s1, s2)
		zipWith(s1, s2) {|a, b| a + b }
	end

	def mul(s1, s2)
		zipWith(s1, s2) {|a, b| a * b }
	end

	def partialSums(s)
		new(s.car) { add(repeat(s.car), partialSums(s.cdr)) }
	end
end

class Series
end

class << Series
	def integrate(s)
		Stream.zipWith(s, Stream.integer) {|a, b| a / b }
	end

	def exp
		Stream.new(1.0) { integrate(exp) }
	end
	def cos
		Stream.new(1.0) { integrate(sin.map{|a| -a }) }
	end
	def sin
		Stream.new(0.0) { integrate(cos) }
	end
end

def sum(array)
	array.inject(0) {|a, b| a + b }
end

ones = Stream.repeat(1)
integer = Stream.integer

p ones.take(10)
p integer.take(10)
p Stream.add(ones, integer).take(10)
p Stream.mul(integer, integer).take(10)
p Stream.partialSums(integer).take(10)

p Stream.partialSums(Series.exp).ref(10)
p Math.exp(1)
p Stream.partialSums(Series.sin).ref(10)
p Math.sin(1)
p Stream.partialSums(Series.cos).ref(10)
p Math.cos(1)

HaskellでSICP3章のストリームを書いてみたらすごかった

言語仕様を見て、これならSICP3章だろうと思ってやってみたら、ほとんどが2行（うち型宣言が1行）で書けてわろた。あとで解説とか書くかもしれないし書かないかもしれない。

module Main where

addStream :: Num a => [a] -> [a] -> [a]
addStream = zipWith (+)

scaleStream :: Num a => a -> [a] -> [a]
scaleStream factor = map (*factor)

mulStream :: Num a => [a] -> [a] -> [a]
mulStream = zipWith (*)

integersStartingFrom :: Num a => a -> [a]
integersStartingFrom n = n : integersStartingFrom (n + 1)

ones :: Num a => [a]
ones = repeat 1

integers :: Num a => [a]
integers = integersStartingFrom 1

partialSums :: Num a => [a] -> [a]
partialSums (x:xs) = x : addStream (repeat x) (partialSums xs)

integrateSeries :: Fractional a => [a] -> [a]
integrateSeries xs = mulStream xs (map recip integers)

expSeries = 1.0 : integrateSeries expSeries
cosSeries = 1.0 : integrateSeries (map negate sinSeries)
sinSeries = 0.0 : integrateSeries cosSeries

mulSeries :: Num a => [a] -> [a] -> [a]
mulSeries (a:as) (b:bs) = a*b :
	addStream (scaleStream a bs) (mulSeries as (b:bs))

sqrtStream :: Fractional a => a -> [a]
sqrtStream x = guesses
	where
		guesses = 1.0 : map improve guesses
		improve guess = average guess (x/guess)
		average a b = (a+b)/2

eularTransform :: Fractional a => [a] -> [a]
eularTransform (x0:x1:x2:xs) = x' : eularTransform (x1:x2:xs)
	where
		x' = x2 - (square (x2 - x1)) / (x0 - 2*x1 + x2)
		square x = x * x

piSummands :: Fractional a => a -> [a]
piSummands n = 1.0/n : map negate (piSummands (n+2))

piStream :: Fractional a => [a]
piStream = scaleStream 4 (partialSums (piSummands 1))

makeTableau :: ([a]->[a]) -> [a] -> [[a]]
makeTableau t xs = xs : makeTableau t (t xs)

acceleratedSequence :: ([a]->[a]) -> [a] -> [a]
acceleratedSequence t xs = map head (makeTableau t xs)

ln2Summands :: Fractional a => a -> [a]
ln2Summands n = 1/n : map negate (ln2Summands (n+1))

ln2Stream :: Fractional a => [a]
ln2Stream = partialSums (ln2Summands 1)

geometricSeris :: Num a => a -> a -> [a]
geometricSeris a r = map ((a*).(r^)) (integersStartingFrom 0)

polySeries :: Num a => a -> [a]
polySeries = geometricSeris 1

applySeries :: Num a => [a] -> a -> [a]
applySeries series x = (partialSums (mulStream series (polySeries x)))

integral :: Num a => [a] -> a -> a -> [a]
integral integrand initial dt = int where
	int = initial : addStream (scaleStream dt integrand) int

solve' :: Num a => (a->a) -> a -> a -> [a]
solve' f y0 dt = y where
	y = integral dy y0 dt
	dy = map f y

solve :: Fractional a => (a->a) -> a -> Int -> a
solve f y0 n = (solve' f y0 dt) !! n
	where dt = 1 / (fromIntegral n)

solve2nd :: Num a => a -> a -> a -> a -> a -> [a]
solve2nd a b dt y0 dy0 = y
	where
		y   = integral dy y0 dt
		dy  = integral ddy dy0 dt
		ddy = addStream (scaleStream a dy) (scaleStream b y)

solve2nd_gen :: Num a => (a -> a -> a) -> a -> a -> a -> [a]
solve2nd_gen f dt y0 dy0 = y
	where
		y   = integral dy y0 dt
		dy  = integral ddy dy0 dt
		ddy = zipWith f dy y