jpp/lab5/zad1/zad1.hs
2024-06-21 16:18:26 +02:00

78 lines
2.1 KiB
Haskell

import Data.List (nub)
binomial :: (Integral n) => n -> n -> n
binomial n 0 = 1
binomial n k
| n == k = 1
| otherwise = binomial (n - 1) k + binomial (n - 1) (k - 1)
-----------------------------------------------
binomial2 :: Int -> Int -> Int
binomial2 n k = triangle !! n !! k
where
triangle = iterate next_row [1]
next_row row = zipWith (+) ([0] ++ row) (row ++ [0])
-----------------------------------------------
merge :: Ord a => [a] -> [a] -> [a]
merge xl [] = xl
merge [] yl = yl
merge (x:xl) (y:yl)
| x <= y = x:merge xl (y:yl)
| otherwise = y:merge (x:xl) yl
mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [a] = [a]
mergesort xl = merge (mergesort (first_half xl)) (mergesort (second_half xl))
first_half xl = let { n = length xl } in take (div n 2) xl
second_half xl = let { n = length xl } in drop (div n 2) xl
------------------------------------------------
gcde :: (Integral a) => a -> a -> (a, a, a)
gcde 0 b = (b, 0, 1)
gcde a b =
let (g, x, y) = gcde (mod b a) a in (g, y - (div b a) * x, x)
de :: (Integral a) => a -> a -> (a, a, a)
de a b = let (g, x, y) = gcde a b in (x, y, g)
------------------------------------------------
prime_factors :: (Integral a) => a -> [a]
prime_factors n = factorize n 2
factorize :: (Integral a) => a -> a -> [a]
factorize 1 _ = []
factorize n factor
| mod n factor == 0 = factor : factorize (div n factor) factor
| otherwise = factorize n (factor + 1)
------------------------------------------------
_gcd :: Integral a => a -> a -> a
_gcd 0 b = b
_gcd a b = _gcd (mod b a) a
is_coprime :: Integral a => a -> a -> Bool
is_coprime a b = _gcd a b == 1
totient :: Integral a => a -> a
totient n = fromIntegral (length (filter (is_coprime n) [1..n]))
------------------------------------------------
totient2 :: Integral a => a -> a
totient2 n = foldl (\acc p -> div (acc * (p - 1)) p) n (nub (prime_factors n))
------------------------------------------------
primes :: Integral a => a -> [a]
primes n = sieve [2..n]
where
sieve [] = []
sieve (x:xs) = x : sieve [y | y <- xs, mod y x /= 0]