久我山菜々 nna774

#利用してるサービスの(ある程度の)まとめ

##Twitter https://twitter.com/nonamea774

#*** Combinator Birds Advent Calender ***

はじめに

このAdvent Calenderは，Combinator Birds(Combinator論理)についての知識が全くない様な人に対して，Combinator Birdsを紹介するノリで書かれています．できるだけ複雑な知識は仮定しないようにはしていますが，わかりにくいところ等があったらごめんなさい．

この記事の中には幾つもの誤りが含まれている可能性があります．おかしいところがあれば遠慮なく突っ込んでください．

Combinator とは，難しく言うと、「自由変数を含まないラムダ式」あたりになるんでしょうか．
正確なことや細かいことはおいておいて，とりあえずCombinatorの世界に触れていただくことをメインに考えてこの記事を書くこととします．

	******** ****** ********
	* この公開鍵は失効しました... *
	******** ****** ********


	------------------------------
	pub 1024D/EB161DAC 2012-07-29
	Key fingerprint = EF2F AB4D 8FA0 ABB5 9CED B5A1 3974 272B EB16 1DAC
	uid NoNameA 774 (NNN77) <[email protected]>
	sub 4096g/32C1FE5A 2012-07-29

	-- オセロ
	--import Data.Functor
	import Maybe
	import Control.Monad

	data Color = Black \| White deriving (Eq, Show, Read)

	type Cell = Maybe Color

	type Board = [[ Cell ]]

	{-# OPTIONS -fglasgow-exts #-}

	i :: forall a. a -> a
	i = \x -> x

	k :: forall a b. a -> b -> a
	k = \x -> \y -> x

	s :: forall a b c. (a -> b -> c) -> (a -> b) -> a -> c
	s = \x -> \y -> \z -> x z $ y z

	The B, C, K, W system is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W.
	BCKWシステムとは、B、C、K、Wの四つの組み込みコンビネータを持つコンビネータ算法の一種である。
	This system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry (1930).
	このシステムは、ハスケル・カリーによって
	The combinators are defined as follows:
	四つのコンビネータは以下のように定義される。
	B x y z = x (y z)
	C x y z = x z y
	K x y = x
	W x y = x y y

	SKI combinator calculus is a computational system that may be perceived as a reduced version of untyped lambda calculus.
	SKIコンビネータ算法とは、型無しラムダ算法の単純化されたものと言われている計算理論である。
	It can be thought of as a computer programming language, though it is not useful for writing software.
	SKIコンビネータは、大きなプログラムを書くのには向いていないが、プログラミング言語と見ることもできる。
	Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language.
	しかし、これはアルゴリズムの理論としては重要なものである。なぜなら、とても単純ではあるが、チューリング完全であるからである。
	All operations in lambda calculus are expressed in SKI as binary trees whose leaves are one of the three symbols S, K, and I (called combinators).
	全てのラムダ式は、SKIの二分木として表すことができる。それらの葉はコンビネータと呼ばれるSKIの三つである。
	In fact, the symbol I is added only for convenience, and just the other two suffice for all of the purposes of the SKI system.
	実は、Iコンビネータは、利便性の為に存在しているに過ぎない。残りの二つだけで全てのラムダ式をSKIコンビネータに書き換えられる。

	#include <stdio.h>
	#include <math.h>
	/* 7 6 7 6 7 2 5 3 0 0 0 0 0 0 0 0 */
	/* 0 3 5 6 7 10 12(ブルーススケール) */
	/* -9 -7 -5 -4 -2 0 2 3 3 2 0 -2 -4 -5 -7 -9 */
	/* 9 9 7 7 6 6 6 6 4 6 7 4 2 2 2 2　*/
	/* 100 -100 100 -100 50 -50 25 -25 12 -12 6 -6 3 -3 0 0 */
	int main(void)
	{
	int i, j;

	-- https://twitpic.com/aynpyj これ
	-- これ自体の詳細は不明

	-- http://ideone.com/25TF8 ここで軽く動かしてる

	{-# OPTIONS
	-XMultiParamTypeClasses
	-XFunctionalDependencies
	-XFlexibleInstances
	#-}

	-- http://www.datapointed.net/visualizations/math/factorization/animated-diagrams/

	data Factor = One \| Product Int Factor deriving (Show,Eq,Read,Ord)

	fact :: Int -> [Int]
	fact 1 = []
	fact n = p : fact (n `div` p)
	where p = head $ filter ((==0).(n `mod`)) [2..]

	factmap :: [Int] -> Factor