На этом шаге мы приведем несколько демострационных примеров.
Приведем несколько демонстрационных примеров.
-- Демонстрация рекурсии с использованием сопоставления -- с образцом на примере функции, возвращающей последний -- элемент одноуровневого списка -------------------------------- last':: [a] -> a last' [] = error "Результат операции не определён" last' [x] = x last' (x:lst) = last' lst ------------------------------ -- Неудачные тестовые примеры: -------------------------------------------- test = last' [1] == 1 && last' [1,2,3] == 3 && last' [[-1],[-2,-3],[-20,3,4]] == [-20,3,4] && last' "abcd" == 'd' ---------------------------------------------------------- test1 = head (tail (head (tail [[-1],[-2,-3],[-20,3,4]]))) test2 = (head.tail.head.tail) [[-1],[-2,-3],[-20,3,4]]
-- Демонстрация полиморфной функции, вычисляющей длину -- списка с использованием рекурсии по аргументам ------------------------------------------------- lstLen:: [a] -> Integer lstLen [] = 0 lstLen (x:xs) = 1+lstLen xs ------------------------------------------------------ -- Демонстрация полиморфной функции, вычисляющей длину -- списка с использованием рекурсии по значению ----------------------------------------------- main:: [a] -> Integer main lst = lstLen' lst 0 where lstLen' [] b = b lstLen' (_:xs) b = lstLen' xs (b+1) ---------------------------------------------------- -- Функция для нахождения длины списка из библиотеки -- Prelude -------------------- length':: [a] -> Int length' = foldl'' (\n _ -> n+1) 0 ---------------------------------------- foldl'':: (a -> b -> a) -> a -> [b] -> a foldl'' f a [] = a foldl'' f a (x:xs) = (foldl'' f $ f a x) xs -------------------------------------------------- -- Демонстрация неполиморфной функции, вычисляющей -- сумму элементов числового списка ----------------------------------- lstSum:: [Int] -> Int lstSum [] = error "Функция не определена" lstSum [x] = x lstSum (x:xs) = x+lstSum xs ------------------------------ -- Неудачные тестовые примеры: ------------------------------------------ test1 = lstLen [] == 0 && lstLen [1] == 1 && lstLen [1,2] == 2 && lstLen [1.2,3.234,0.000001] == 3 && lstLen ['a','b','c','d'] == 4 && lstLen ["a b","cde fg h"] == 2 ------------------------------------------ test2 = lstLen [1..3990] test3 = main [1..5324] test4 = length' [1..6000] ------------------------------------------- test5 = lstSum [2] == 2 && lstSum [1,2,0] == 3 && lstSum [1,2,0,-1,-2] == 0 && lstSum [-100,2,0,-10,-2] == (-110)
-- Функция, возвращающая количество символов -- в списке lst, равных заданному символу s ------------------------------------------- kolEl:: Char -> [Char] -> Int kolEl s lst | null lst || notElem s lst = 0 | head lst==s = 1 + kolEl s (tail lst) | True = kolEl s (tail lst) ---------------------------------------------- kolEl':: Char -> [Char] -> Int kolEl' s lst | null lst || notElem s lst = 0 | last lst==s = 1 + kolEl' s (init lst) | True = kolEl' s (init lst) -- ********************************************* -- Неудачные тестовые примеры: ------------------------------------------ test1 = kolEl 'n' ['a','n'] == 1 && kolEl 'a' ['f','a','b','a'] == 2 && kolEl 'v' ['a','s','d'] == 0 && kolEl 'q' "qwqwqwqweb" == 4 && kolEl ' ' "q wq qw we " == 4 ------------------------------------------- test2 = kolEl' 'n' ['a','n'] == 1 && kolEl' 'a' ['f','a','b','a'] == 2 && kolEl' 'v' ['a','s','d'] == 0 && kolEl' 'q' "qwqwqwqweb" == 4 && kolEl' ' ' "q wq qw we " == 4
-- Нерекурсивная функция, добавляющая элемент -- в конец списка ------------------------------ add_el:: Int -> [Int] -> [Int] add_el a lst = lst ++ [a] ------------------------------------------- -- Рекурсивная функция, добавляющая элемент -- в конец списка ------------------------------- add_el1:: Int -> [Int] -> [Int] add_el1 a [] = [a] add_el1 a (x:xs) = x : add_el1 a xs -- ******************************** -- Неудачные тестовые примеры: ------------------------------------------ test1 = add_el 1 [] == [1] && add_el 1 [2,-3,4] == [2,-3,4,1] && add_el (-2000) [-10,2,-3] == [-10,2,-3,-2000] ------------------------------------------------------- test2 = add_el1 1 [] == [1] && add_el1 1 [2,-3,4] == [2,-3,4,1] && add_el1 (-2000) [-10,2,-3] == [-10,2,-3,-2000] -------------------------------------------------------- test = test1 && test2
-- Демонстрация функции, "переворачивающей" список ------------------------------------------------------- -- (1) с использованием охран (рекурсия по аргументам): ------------------------------------------------------- reverse':: [Int] -> [Int] reverse' lst | null lst = lst | True = reverse' (tail lst) ++ [head lst] ----------------------------------------------------------- -- (2) с использованием охран (рекурсия по значению): ----------------------------------------------------- reverse'':: [Int] -> [Int] -> [Int] reverse'' lst lst1 | null lst = lst1 | True = reverse'' (tail lst) (head lst : lst1) ----------------------------------------------------------- -- (3) с использованием сопоставления с образцом: ------------------------------------------------- lstR:: [Int] -> [Int] lstR [] = [] lstR (x:xs) = lstR xs ++ [x] --------------------------------------------- -- (4) с использованием именованных образцов: --------------------------------------------- lstR1:: [Int] -> [Int] lstR1 [] = [] lstR1 l@(m@x:f@xs) = lstR1 f ++ [m] -- ******************************** -- Неудачные тестовые примеры: ----------------------------------------- test1 = reverse' [1,2,3] == [3,2,1] && reverse' [] == [] && reverse' [1..2500] == reverse [1..2500] --------------------------------------------------- test2 = reverse'' [1..2500] [] == reverse [1..2500] --------------------------------------------------- test3 = lstR [] == [] && lstR [1] == [1] && lstR [1,2,3] == [3,2,1] && lstR [1..32767] == reverse [1..32767] ------------------------------------------------ test4 = lstR1 [] == [] && lstR1 [1] == [1] && lstR1 [1,2,3] == [3,2,1] && lstR1 [1..32767] == reverse [1..32767]
-- Функция, увеличивающая каждый элемент -- числового списка на число n ------------------------------ add:: Int -> [Int] -> [Int] add n [] = [] add n (x:xs) = (x+n) : add n xs -------------------------------------------------- -- Альтернативный вариант функции с использованием -- функционала map -------------------------- f1:: Int -> [Int] -> [Int] f1 n lst = map (+ n) lst ---------------------------------------------------- -- Функция, применяющая функционал map для вычисле- -- ния списка факториалов каждого элемента заданного -- списка --------------------------- f2:: [Integer] -> [Integer] f2 lst = map (fact) lst where fact n | n==0 = 1 | True = n*fact (n-1) -- ************************************ -- Неудачные тестовые примеры: ---------------------------------------- test1 = add 2 [] == [] && add 2 [1] == [3] && add (-1) [-2,-1,0,2,3,4] == [-3,-2,-1,1,2,3] && add (-5) [-10,0,105] == [-15,-5,100] ------------------------------------------- && f1 2 [] == [] && f1 2 [1] == [3] && f1 (-1) [-2,-1,0,2,3,4] == [-3,-2,-1,1,2,3] && f1 (-5) [-10,0,105] == [-15,-5,100] -------------------------------------------------- test2 = f2 [1..5] == [1,2,6,24,120]
-- Функция, возвращающая список, образованный -- перестановкой соседних элементов списка. -- Например: -- [1,2,3,4,5,6] -> [2,1,4,3,6,5] -- [1,2,3] -> [2,1,3] ---------------------------- lstRev:: [Int] -> [Int] lstRev [] = [] lstRev [x] = [x] lstRev (x:y:xs) = y : x : lstRev xs ----------------------------------- -- Неудачные тестовые примеры: ------------------------------------------------ test = lstRev [1,2,33,4,5,6] == [2,1,4,33,6,5] && lstRev [2,3,4,5,6] == [3,2,5,4,6]
import List (delete) ------------------------------------------------------ -- Демонстрация использования сопоставления с образцом -- на примере удаления элементов из заданного списка, -- расположенных на чётных местах --------------------------------- ud1:: [a] -> [a] ud1 [] = [] ud1 [x] = [x] ud1 (x:y:lst) = x : ud1 lst --------------------------------------------------- -- Демонстрация использования охранных выражений на -- примере удаления элементов из заданного списка, -- расположенных на чётных местах --------------------------------- ud2:: [a] -> [a] ud2 lst | null lst = [] | null (tail lst) = lst | True = head lst : ud2 (tail (tail lst)) ------------------------------------------------------------ -- Демонстрация использования сопоставления с образцом -- на примере удаления элементов из заданного списка, -- расположенных на нечётных местах ----------------------------------- ud3:: [a] -> [a] ud3 [] = [] ud3 [x] = [] ud3 (x:y:lst) = y : ud3 lst ----------------------------------------------- -- Функция удаляет все элементы x из списка lst -- (неэффективная функция) ------------------------------------- delAll x lst | not $ elem x lst = lst | True = delAll x (delete x lst) --------------------------------------------------------- -- Функция удаляет все элементы x из списка lst -- (более эффективная функция) --------------------------------- delAll' x lst | null lst = lst | x==head lst = delAll' x (tail lst) | True = (:) (head lst) (delAll' x (tail lst)) -- **************************************************************** -- Неудачные тестовые примеры: -------------------------------------------------- test1 = ud1 [2] == [2] && ud1 [2,-2] == [2] && ud1 [2,-2,-3,3,-4] == [2,-3,-4] && ud1 [1,2,3,4,5,6,7,8,9] == [1,3,5,7,9] && ud1 [[1],[2,3],[4,5,6,7],[8],[9]] == [[1], [4,5,6,7], [9]] ------------------------------------------ && ud2 [2] == [2] && ud2 [2,-2] == [2] && ud2 [2,-2,-3,3,-4] == [2,-3,-4] && ud2 [1,2,3,4,5,6,7,8,9] == [1, 3, 5, 7, 9] && ud2 [[1],[2,3],[4,5,6,7],[8],[9]] == [[1], [4,5,6,7], [9]] ------------------------------------------ && ud3 [2] == [] && ud3 [2,-2] == [-2] && ud3 [2,-2,-3,3,-4] == [-2,3] && ud3 [1,2,3,4,5,6,7,8,9] == [ 2, 4, 6, 8 ] && ud3 [[1],[2,3],[4,5,6,7],[8],[9]] == [ [2,3], [8] ] ------------------------------------------- test2 = putStr (ud1 []) test3 = putStr (ud2 []) ----------------------------------- test4 = delAll 'a' "1a2a3a4a5a6a7a" test5 = delAll' 'a' "1a2a3a4a5a6a7a"
На следующем шаге мы приведем перечень задач для самостоятельного решения.
