Re: kylix 2

[Dmitry Astapov <adept@umc.com.ua>]

Evening, Denis. 

Denis Dzyubenko <shad@mail.kubtelecom.ru> 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: adept@umc.com.ua
GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498  2B08 7867 4860 F5D7 639D