Haskell整数演算の実装

長い間、自然数は、一般的な数字のように、定義できない概念であると信じられていました。 それらは直感によってのみ知ることができます。 ただし、現在、すべての数値セットは明確に定義されています。



最も便利な方法は、ペアノによって決定することです。 ただし、それは可算セットを定義しますが、明確な構築セットを提供しません。 別のアプローチは、自然数を特別な基数、つまり有限集合の基数として定義することです。 3番目は教会の数字です。



上記のすべての定義について、数値を事前定義済みの概念と見なすべきかどうかを検討することをお勧めします。 突然、ある時点で全世界がひっくり返り、コンピューターが数値データを保存できなくなることを想像してみましょう。 その後、プログラマは非常に病気になります。 ただし、上記のすべてを覚えておけば、すぐにすべてが適切に配置されます。 最初から定義する例として、Haskellに自然数と整数の型を実装します。 ベースとして、リストの概念を取り入れてnatを定義します。 その長さとしての数値（後者が有限である場合）。



data [a] = [] | a:[a] -- , [] : — , [] —

head x:_ = x; tail _:x = x;

data () = () -- ,







ちょっとした理論：

リストの終了:: = x：（x == []）|| （テールx-最終）

リストの等価性は、 []==[] = True; (a:as)==(b:bs) = (a==b) && (as==bs)



によって決定され[]==[] = True; (a:as)==(b:bs) = (a==b) && (as==bs)



[]==[] = True; (a:as)==(b:bs) = (a==b) && (as==bs)



要素が比較可能である場合。

集合論的アプローチと同様に、リストの「等次元性」の概念を定義します。

a〜b :: =（a == [] && b == []）|| （テールa〜テールb）

この関係は同等（対称-推移-再帰）であるため、各リストの同等クラスを構築できます。 ベースについては、リストのシーケンス[]、[（）]、[（）、（）]、[（）、（）、（）]、...、つまりセット[（）]を使用します。

それらは互いに等しくはありませんが、有限リストには同じ長さのセット[（）]からのリストがあります。 そのため、[（）]からの代表と同等クラスを識別します。



type N = [](); -- [()]

data Natural = MkN N; -- ,







自然数のいくつかの基本的な操作を説明します。

toList :: Natural -> N; --

toList (MkN x) = x;

incN :: Natural -> Natural; -- ,

incN = MkN.(():).toList;



--

sumN :: Natural -> Natural -> Natural;

sumN (MkN x) = MkN.(++x).toList;



copy :: a->[a]; copy x = x: copy x;

concatAll :: [[a]] -> [a];

concatAll = foldl(++)[];

table :: Natural -> a -> [a]; --

table xy = map (\_->y) $ toList x;



-- a*b a b (),

-- b a ( , )

-- concatAll

multN :: Natural -> Natural -> Natural;

multN xy = MkN $ concatAll $ table x (toList y);

decN :: Natural -> Natural;

decN (MkN(_:xs)) = MkN xs;

decN (MkN []) = error "Cannot decrease 0 staying being Natural";

zeroN :: Natural;

zeroN = MkN [];

oneN :: Natural;

oneN = MkN [()];

equalN :: Natural -> Natural -> Bool;

equalN (MkN a) (MkN b) = a==b;







さらにいくつかの機能が残っています。

subN :: Natural -> Natural -> Natural;

subN xy | y==oneN = decN x -- x-1=decN(x)

| y/=zeroN = decN $ subN x $ decN y -- xy=(x-1)-(y-1)

| True = x; -- x-0=x

divmodN :: Natural -> Natural -> (Natural, Natural);

divmodN (MkN []) _ = error "cannot divide by zero";

divmodN base x | moreThanN base x = (zeroN, x)

| True = let (d,m) = divmodN base (subN x base) in (incN d,m);

moreThanN :: Natural -> Natural -> Bool;

moreThanN (MkN []) _ = False;

moreThanN _ (MkN []) = True;

moreThanN xy = moreThanN (decN x) (decN y);

lengthN :: [a] -> Natural;

lengthN = MkN . map (\_->());







次に、整数の概念に一般化します。

data Integer = Positive Natural | Negative Natural;





自然な引数のいくつかの関数を一般化します：

absInt :: Integer -> Natural;

absInt (Positive x) = x;

absInt (Negative x) = x;

equalInt :: Integer -> Integer -> Bool;

equalInt (Positive x) (Positive y) = x `equalN` y;

equalInt (Negative x) (Negative y) = x `equalN` y;

equalInt (Negative x) (Positive y) | x==zeroN && y==zeroN = True;

equalInt (Positive x) (Negative y) | x==zeroN && y==zeroN = True;

equalInt _ _ = False;

negate :: Integer -> Integer;

negate (Positive x) = (Negative x);

negate (Negative x) = (Positive x);

sumInt :: Integer -> Integer -> Integer;

sumInt (Positive x) (Positive y) = Positive (sumN xy);

sumInt (Positive x) (Negative y) = if x `moreThanN` y then Positive (subN xy) else Negative (subN yx);

sumInt (Negative x) (Positive y) = if y `moreThanN` x then Positive (subN yx) else Negative (subN xy);

sumInt (Negative x) (Negative y) = Negative (sumN xy);







スペースを節約するために、これ以上説明しません。



最終タッチ：文字列への変換。 この例では、3進法を（図の長さに沿って）実装しています

figures = ['0', '1', '2'];

naturalseries = zeroInt : map incInt naturalseries;

figuretoInt = compare $ zip figures naturalseries where{compare ((a,b):c) x | a==x = b | True = compare cx;};

inttoFigure = getElement figures where {getElement (h:t) n = if n==zeroInt then h else getElement t $ decInt n;};

base :: Integer;

base = lengthInt figures;

showInt :: Integer -> [Char];

showInt x | x<zeroInt = '-' : showInt (negate x)

| x==zeroInt = "0"

| x<base = [inttoFigure x]

| True = let (d,m) = divmodInt base x

in (show d) ++ [inttoFigure m];

readInt :: [Char] -> (Integer, [Char]);

readInt "" = error "No integer to read on input";

readInt str@(f:r)

| f=='-' = let (i,s) = readInt r in (negate i,s)

| f=='+' = readInt r

| True = let (num,rest) = split str in (parse $ map figuretoInt num, rest);

split :: [Char] -> ([Char],[Char]);

split "" = ("","");

split (x:y) | x~->figures = let (a,b)=split y in (x:a,b)

| True = ("", x:y);

parse :: [Integer] -> Integer;

parse = foldl (\g h->sumInt h $ multInt base g) zeroInt;







リストメンバーシップ関数が使用されました(~->) :: (Eq a) => a -> [a] -> Bool;

a ~-> [] = False;

a ~-> (b:c) = (a==b) || (a ~-> c);



(~->) :: (Eq a) => a -> [a] -> Bool;

a ~-> [] = False;

a ~-> (b:c) = (a==b) || (a ~-> c);







それはすべて保存されています！



PS何も深刻ではありません。 私は、ほとんどどこでも基本的であり、多くの言語で再定義を許可していないタイプが、ゼロから簡単に定義できることを示したかっただけです。

それにもかかわらず、私はPPS Boolを使用したので、このタイプはビットの類似物であると常に言うことができ、その後、何らかの方法でバイト、ワードなどの類似物を与える8、16、32、64要素をグループ化できます...