Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
223 lines (165 sloc) 5.86 KB
{-# LANGUAGE NoImplicitPrelude #-}
module ITMOPrelude.Primitive where
import Prelude (Show,Read)
---------------------------------------------
-- Синтаксис лямбда-выражений
-- Эквивалентные определения
example1 x = x
example1' = \x -> x
example1'' = let y = \x -> x in y
example1''' = y where
y = \x -> x
-- Снова эквивалентные определения
example2 x y = x %+ y
example2' x = \y -> x %+ y
example2'' = \x -> \y -> x %+ y
example2''' = \x y -> x %+ y
example2'''' = let z = \x y -> x %+ y in z
example2''''' = z where
z x = \y -> x %+ y
-- Зацикленное выражение
undefined = undefined
-- Ниже следует реализовать все термы, состоящие из undefined заглушки.
-- Любые термы можно переписывать (natEq и natLt --- хорошие кандидаты).
-------------------------------------------
-- Примитивные типы
-- Тип с единственным элементом
data Unit = Unit deriving (Show,Read)
-- Пара, произведение
data Pair a b = Pair { fst :: a, snd :: b } deriving (Show,Read)
-- Вариант, копроизведение
data Either a b = Left a | Right b deriving (Show,Read)
-- Частый частный случай, изоморфно Either Unit a
data Maybe a = Nothing | Just a deriving (Show,Read)
-- Частый частный случай, изоморфно Either Unit Unit
data Bool = False | True deriving (Show,Read)
-- Следует отметить, что встроенный if с этим Bool использовать нельзя,
-- зато case всегда работает.
-- Ну или можно реализовать свой if
if' True a b = a
if' False a b = b
-- Трихотомия. Замечательный тип, показывающий результат сравнения
data Tri = LT | EQ | GT deriving (Show,Read)
-------------------------------------------
-- Булевы значения
-- Логическое "НЕ"
not :: Bool -> Bool
not True = False
not False = True
infixr 3 &&
-- Логическое "И"
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
infixr 2 ||
-- Логическое "ИЛИ"
(||) :: Bool -> Bool -> Bool
True || _ = True
False || x = x
-------------------------------------------
-- Натуральные числа
data Nat = Zero | Succ Nat deriving (Show,Read)
natZero = Zero -- 0
natOne = Succ Zero -- 1
-- Сравнивает два натуральных числа
natCmp :: Nat -> Nat -> Tri
natCmp = undefined
-- n совпадает с m
natEq :: Nat -> Nat -> Bool
natEq Zero Zero = True
natEq Zero (Succ _) = False
natEq (Succ _) Zero = False
natEq (Succ n) (Succ m) = natEq n m
-- n меньше m
natLt :: Nat -> Nat -> Bool
natLt Zero Zero = False
natLt Zero (Succ m) = True
natLt (Succ n) Zero = False
natLt (Succ n) (Succ m) = natLt n m
infixl 6 +.
-- Сложение для натуральных чисел
(+.) :: Nat -> Nat -> Nat
Zero +. m = m
(Succ n) +. m = Succ (n +. m)
infixl 6 -.
-- Вычитание для натуральных чисел
(-.) :: Nat -> Nat -> Nat
n -. m = undefined
infixl 7 *.
-- Умножение для натуральных чисел
(*.) :: Nat -> Nat -> Nat
Zero *. m = Zero
(Succ n) *. m = m +. (n *. m)
-- Целое и остаток от деления n на m
natDivMod :: Nat -> Nat -> Pair Nat Nat
natDivMod n m = undefined
natDiv n = fst . natDivMod n -- Целое
natMod n = snd . natDivMod n -- Остаток
-- Поиск GCD алгоритмом Евклида (должен занимать 2 (вычислителельная часть) + 1 (тип) строчки)
gcd :: Nat -> Nat -> Nat
gcd = undefined
-------------------------------------------
-- Целые числа
-- Требуется, чтобы представление каждого числа было единственным
data Int = UNDEFINED deriving (Show,Read)
intZero = undefined -- 0
intOne = undefined -- 1
intNegOne = undefined -- -1
-- n -> - n
intNeg :: Int -> Int
intNeg = undefined
-- Дальше также как для натуральных
intCmp :: Int -> Int -> Tri
intCmp = undefined
intEq :: Int -> Int -> Bool
intEq = undefined
intLt :: Int -> Int -> Bool
intLt = undefined
infixl 6 .+., .-.
-- У меня это единственный страшный терм во всём файле
(.+.) :: Int -> Int -> Int
n .+. m = undefined
(.-.) :: Int -> Int -> Int
n .-. m = n .+. (intNeg m)
infixl 7 .*.
(.*.) :: Int -> Int -> Int
n .*. m = undefined
-------------------------------------------
-- Рациональные числа
data Rat = Rat Int Nat
ratNeg :: Rat -> Rat
ratNeg (Rat x y) = Rat (intNeg x) y
-- У рациональных ещё есть обратные элементы
ratInv :: Rat -> Rat
ratInv = undefined
-- Дальше как обычно
ratCmp :: Rat -> Rat -> Tri
ratCmp = undefined
ratEq :: Rat -> Rat -> Bool
ratEq = undefined
ratLt :: Rat -> Rat -> Bool
ratLt = undefined
infixl 7 %+, %-
(%+) :: Rat -> Rat -> Rat
n %+ m = undefined
(%-) :: Rat -> Rat -> Rat
n %- m = n %+ (ratNeg m)
infixl 7 %*, %/
(%*) :: Rat -> Rat -> Rat
n %* m = undefined
(%/) :: Rat -> Rat -> Rat
n %/ m = n %* (ratInv m)
-------------------------------------------
-- Операции над функциями.
-- Определены здесь, но использовать можно и выше
infixr 9 .
f . g = \ x -> f (g x)
infixr 0 $
f $ x = f x
-- Эквивалентные определения
example3 a b c = gcd a (gcd b c)
example3' a b c = gcd a $ gcd b c
example3'' a b c = ($) (gcd a) (gcd b c)
-- И ещё эквивалентные определения
example4 a b x = (gcd a (gcd b x))
example4' a b = gcd a . gcd b