Задаци за вежбу¶

positive :: Num a => [a] -> [a]
positive [] = []
positive (x:xs) = (if x > 0 then x : positive xs else positive xs)

Решење помоћу filter је неупоредиво јасније и једноставније.

positive :: Num a => [a] -> [a]
positive = filter (>0)

square_roots :: [Double] -> [Double]
square_roots [] = []
square_roots (x:xs) = sqrt x : square_roots xs

Решење помоћу map је неупоредиво јасније и једноставније.

square_roots :: [Double] -> [Double]
square_roots = map sqrt

До решења се једноставно долази ако се примети да се резултат добија тако што се резултат иницијализује на празну листу, затим се обрађује једна по једна листа из дате листе и у саком кораку се резултат ажурира тако што се текућа листа надовеже на почетак резултата.

my_concat :: [[a]] -> [a]
my_concat = foldr (++) []

Користимо уобичајени алгоритам факторизације бројева који је обрађен у другом разреду.

List<ulong> PrimeFactors(ulong n)
{
   List<ulong> factors = new List<ulong>();
   ulong d = 2;
   while (d * d <= n)
   {
       if (n % d == 0)
       {
           factors.Add(d);
           n /= d;
       } else
         d++;
   }
   if (n > 1)
      factors.Add(n);
   return factors;
}

Исти се алгоритам лако изражава рекурзивно и имплементира у језику Haskell:

primeFactors :: Integer -> [Integer]
primeFactors n = factorize n 2
  where
     factorize k d
        | d * d > k        = [k | k > 1]
        | k `mod` d == 0   = d : factorize (k `div` d) d
        | otherwise        = factorize k (d + 1)

Прикажимо и извршавање овог алгоритма на једном примеру:

primeFactors 168 =
factorize 168 2 =
2 : factorize 84 2 =
2 : 2 : factorize 42 2 =
2 : 2 : 2 : factorize 21 2 =
2 : 2 : 2 : factorize 21 3 =
2 : 2 : 2 : 3 : factorize 7 3 =
2 : 2 : 2 : 3 : 7 =
[2, 2, 2, 3, 7]

Основни алгоритам је да се крене од празног стека, да се пролази кроз листу токена (бројева или ознака операција) добијених разбијањем израза и да се у сваком кораку стек ажурира имајући у виду тренутни токен. Ако је тренутни токен број, тада се његова бројна вредност додаје на стек, а ако је оператор, тада се скидају две вредности са врха стека, на њих се примењује операција и резултат се додаје на почетак стека. Резултат се на крају налази на врху стека (под претпоставком да је израз исправн, то ће бити и једини елемент на стеку).

Прво треба да буде примењена функција words. Након тога се врши обрада једног по једног елемента листе слева надесно, ажурирајући при том стек. Јасно је да је у питању операција foldl, при чему морамо да дефинишемо помоћну функцију updateStack која врши ажурирање стека. Њена дефиниција је једноставна (анализирамо случајеве и користимо поклапање шаблона). При том је важно напоменути да ћемо стек имплементирати уз помоћ листе, где ће врх стека бити на почетку листе (да бисмо ефикасно могли скидати елементе са врха стека и додавати их на стек). На крају издвајамо елемент са врха стека (функцијом head, јер је у питању листа).

rpn :: [Char] -> Integer
rpn = head . foldl updateStack [] . words
  where
    updateStack (x : y : xs) "+" = (x + y) : xs
    updateStack (x : y : xs) "*" = (x * y) : xs
    updateStack          xs  num = read num : xs

Празна листа је једини префикс празне листе. Ако одредимо све префиксе репа листе, тада све непразне префиксе листе можемо добити њиховим проширивањем тако што се глава листе дода на почетак. Поред њих, не треба да заборавимо и на празан префикс. На пример, ако имамо листу [1, 2, 3], префикси репа листе (рекурзивно одређени) су [[], [2], [2, 3]]. Дописивањем јединице на сваки од њих добијамо [[1], [1, 2], [1, 2, 3]]. Додавањем празне листе на почетак, добијамо листу [[], [1], [1, 2], [1, 2, 3]] која садржи све префиксе полазне листе. Дописивање главе на почетак сваке листе можемо лако остварити применом функције map.

my_prefixes :: [a] -> [[a]]
my_prefixes [] = [[]]
my_prefixes (x:xs) = [] : map (x:) (my_prefixes xs)

Задатак решавамо рекурзијом по дужини варијације. Претпоставимо да смо рекурзивно направили све варијације дужине \(n-1\). Сваку од њих треба на све могуће начине проширити елементима дате листе. То се најједноставније може изразити компрехенсијом. Излаз из рекурзије су варијације дужине 0. Тај случај је пипав јер резултат није празна листа, већ листа која садржи празну листу (увек постоји тачно једна варијација дужине 0 и она је празна).

variations xs 0 = [[]]
variations xs n = let vs = variations xs (n-1)
                   in [x:v | x <- xs, v <- vs]

Дефинисати рекурзивну функцију која уз помоћ функције dropWhile уклања све узастопне дупликате из листе. На пример, за листу [1, 1, 2, 2, 1, 1, 1] треба да се добије резултат [1, 2, 1].

Уклањањем дупликата из празне листе добија се празна листа. Ако је листа непразна њен први елемент (глава) се задржава, уклањају се сва његова појављивања са почетка репа (за то се може употребити функција dropWhile), након чега се рекурзивно уклањају сви дупликати из репа.

remConsecutiveDups :: Eq a => [a] -> [a]
remConsecutiveDups [] = []
remConsecutiveDups (x:xs) = x : remConsecutiveDups (dropWhile (== x) xs)