Evening, Denis. Denis Dzyubenko <[EMAIL PROTECTED]> 13:10 9/1/2003 wrote:
DA>> DA>> И как на C правильно реализуется map и fold? А так, чтобы было type-safe? А DA>> рекурсивные функции? А с tail-recursive оптимизацией? DD> что есть map, fold и tail-recursive оптимизация? Функции такого вида (я, да простят меня, решил демонстрировать на примерах...): map :: (a -> b) -> [a] -> [b] (дали функцию и список, получили список, к каждому эл-ту которого применена эта ф-я) foldl :: (a -> b -> a) -> a -> [b] -> a foldr :: (a -> b -> b) -> b -> [a] -> b (дали ф-ю f, начальное значение z и список [x1,x2,...], получили результат f(f(f(z,x1),x2),x3),... или f(x1,f(x2,f(x3,...(f(x_n,z)))))) Примеры: Prelude> map (*2) [1,2,3] [2,4,6] Prelude> map (\x -> take x (repeat x)) [1,2,3] [[1],[2,2],[3,3,3]] Prelude> map sort [[3,2,1],[14,1,20],[3,5]] [[1,2,3],[1,14,20],[3,5]] Prelude> foldr (+) 0 [1,2,3,4] 10 Prelude> foldr (*) 1 [1,2,3,4] 24 Это - базовые строительные блоки для функционального программирования. Примеры: maximum :: [a] -> a (выбор макс. эл-та) maximum lst = foldl max xs where max x y = if x > y then x else y -- inits xs returns the list of initial segments of xs, shortest first. -- e.g., inits "abc" == ["","a","ab","abc"] inits :: [a] -> [[a]] inits [] = [[]] inits (x:xs) = [[]] ++ map (x:) (inits xs) Tail-recursive оптимизация - способность выполнять функции, последним действием которых является рекурсивынй вызов, в константном объеме памяти. DA>> ЗЫ DA>> Пост-фактум прошу прощения за то, что письмо состоит из одних "каверзных" DA>> вопросов. Но я не ставил себе целью объяснить - скорее, зародить сомнение :) DD> а где же найти ответы на эти каверзные вопросы? В литературе, в интернете, в чужом коде ... -- Dmitry Astapov //ADEpt E-mail: [EMAIL PROTECTED] GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D
