हास्केल पूर्णांक अंकगणितीय कार्यान्वयन

लंबे समय तक यह माना जाता था कि प्राकृतिक संख्याएं, सामान्य रूप से संख्याएं, अनिश्चित अवधारणाएं हैं, प्राथमिक; उन्हें केवल अंतर्ज्ञान से जाना जा सकता है। हालांकि, वर्तमान में, सभी संख्यात्मक सेट स्पष्ट रूप से परिभाषित किए गए हैं।



सबसे सुविधाजनक तरीका पीनो द्वारा निर्धारित किया जाता है। हालाँकि, यह गिनती करने योग्य सेटों को परिभाषित करता है, लेकिन एक निश्चित निर्माण सेट नहीं देता है। एक अन्य दृष्टिकोण प्राकृतिक संख्या को एक विशेष कार्डिनल के रूप में परिभाषित करना है, अर्थात् एक परिमित सेट की कार्डिनैलिटी। तीसरा है चर्च अंक।



मैं सुझाव दूंगा कि आप इस बारे में सोचें कि क्या उपरोक्त सभी परिभाषाओं के लिए, संख्याओं को पूर्वनिर्धारित अवधारणा माना जाना चाहिए। आइए कल्पना करें कि अचानक एक बिंदु पर पूरी दुनिया उलट जाएगी और कोई भी कंप्यूटर संख्यात्मक डेटा को स्टोर करने में सक्षम नहीं होगा। तब प्रोग्रामर बहुत बीमार होंगे। लेकिन आपको बस उपरोक्त सभी को याद रखना होगा और तुरंत सबकुछ ठीक हो जाएगा। हम हस्केल पर प्राकृतिक और पूर्णांक संख्याओं के प्रकार को लागू करते हैं, खरोंच से परिभाषा के उदाहरण के रूप में। एक आधार के रूप में, हम एक सूची की अवधारणा लेते हैं और नेट को परिभाषित करते हैं। इसकी लंबाई के रूप में एक संख्या (बशर्ते कि परिमित परिमित हो)।



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)



बशर्ते कि तत्व तुलनीय हों।

सेट-थ्योरैटिक दृष्टिकोण के समान, हम सूचियों की "समानता" की अवधारणा को परिभाषित करते हैं, अर्थात्:

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);







मैं अंतरिक्ष को बचाने के लिए आगे नहीं दूंगा।



अंतिम स्पर्श: स्ट्रिंग में रूपांतरण। उदाहरण टर्नरी सिस्टम को लागू करता है (आंकड़ों की लंबाई के साथ)

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);







वह सब बच गया!



पुनश्च कुछ भी गंभीर नहीं है। मैं सिर्फ यह दिखाना चाहता था कि वे प्रकार जो लगभग हर जगह बुनियादी हैं, और कई भाषाओं में पुनर्वितरण की अनुमति नहीं है, आसानी से परिभाषित किया जा सकता है जैसे कि खरोंच से।

फिर भी, मैंने पीपीएस बूल का उपयोग किया है, इसलिए आप हमेशा कह सकते हैं कि यह प्रकार थोड़ा सा का एक एनालॉग है, तो आप किसी तरह 8, 16, 32, 64 तत्वों का समूह बना सकते हैं, जो कि बाइट, वर्ड, ...