dmz>>def makeHuffTree(symbolTupleList):
BZ>при всём нашем уважении к питону это построитель дерева, а не генератор кодов
Уел. Если приделать перестроение дерева, что бы удобно генерить код, то в объеме кода разницы нет с тем-же окамлом.
# module Huffman : sig
val encode : (int * int) list -> string -> (bool -> unit) -> unit
val decode : (int * int) list -> (unit -> bool option) -> string
end = struct
type node =
| Leaf of int
| Node of t * t
and t = int * node
let rec build roots =
match List.sort compare roots with
| [] -> invalid_arg "Huffman"
| [h] -> h
| (p1, _ as t1)::(p2, _ as t2)::t ->
build((p1 + p2, Node(t1, t2)) :: t)
let mk_tree freqs =
build((0, Leaf(-1))::List.map (fun (p, c) -> p, Leaf c) freqs)
let rec mk_table = function
| _, Leaf c -> [c, []]
| _, Node(t1, t2) ->
let cons b (c, t) = c, b::t in
List.map (cons true) (mk_table t1) @
List.map (cons false) (mk_table t2)
let encode freqs string write_bit =
let table = mk_table(mk_tree freqs) in
let rec emit char =
let byte = Char.code char in
List.iter write_bit (List.assoc byte table) in
String.iter emit string;
List.iter write_bit (List.assoc (-1) table)
let rec decode_aux read_bit t tree buf =
match t with
| _, Leaf(-1) -> Buffer.contents buf
| _, Leaf byte ->
Buffer.add_char buf (Char.chr byte);
decode_aux read_bit tree tree buf
| _, Node(t1, t2) ->
match read_bit(), t1, t2 with
| None, _, _ -> invalid_arg "decode"
| Some true, t, _ | Some false, _, t ->
decode_aux read_bit t tree buf
let decode freqs read_bit =
let tree = mk_tree freqs in
decode_aux read_bit tree tree (Buffer.create 1024)
end;;
module Huffman :
sig
val encode : (int * int) list -> string -> (bool -> unit) -> unit
val decode : (int * int) list -> (unit -> bool option) -> string
end
Re[7]: RAII in higher-order languages (Мастер-класс по ФП)
Здравствуйте, dmz, Вы писали:
dmz> Мне вот интересно, почему в окамле нет встроенных функций group и т.п.
У него стандартная библиотека вообще очень бедная по сравнению с хаскеллом.
Но при желании можно подключить такую штуку: http://github.com/kig/preludeml/tree/master/prelude.ml
хотя мне в большинстве случаев хватает ExtLib + немного отсебятины.
Здравствуйте, dmz, Вы писали:
dmz>def makeHuffTree(symbolTupleList):..
А, ясно. При наличии реализованной бинарной кучи на С++ и др. языках получится то же самое.
Вообще, пока что мы в этом треде видим, что короче и проще те решения, где есть подходящие готовые библиотечные функции.
DM>А, ясно. При наличии реализованной бинарной кучи на С++ и др. языках получится то же самое.
Ну так оно в питоне в стандартную библиотеку входит — тащить ниоткуда не надо.
DM>Вообще, пока что мы в этом треде видим, что короче и проще те решения, где есть подходящие готовые библиотечные функции.
Ну да, в общем. ФП помогает решать проблемы, которые появляются при определенной критической массе кода, или сложности, или
необходимости модификации. Это никак в рамках топика не рассмотришь, остается только или принять на веру, или самому напороться.
Здравствуйте, BulatZiganshin, Вы писали:
BZ> есть список слов. надо записать в файл "a" все слова, начинающиеся на букву 'a', в файл "b" — слова на 'b' и т.д. вплоть до z
Решил вспоминть синтаксис haskell и, проигнорировав api для записи в файл, накалякал такое решение:
Задачка, конечно, игрушечная, но что было бы будь это "реальная" задача. Как бы я тогда её решал?
Прежде всего обобщил бы постановку задачи:
Дано: источник данных, критерий разбиения данных на группы
Надо: данные разбить на группы, обработать данные в группах.
В итоге на свет явлись бы интерфейсы и классы:
interface IGroup<T>
{
boolean add(T data); //true - data accepted, false - not accepted.void done(); //no more data, group finished.
}
//обработчик произвольных данных interface IProcessor<T>
{
void add(T data);
void done(); //no more data
}
//пишет в файлclass FileProcessor implements IProcessor<String>
{
FileProcessor(String fileName) { ... }
...
}
//пишет в консольclass ConsoleProcessor implements IProcessor<String>
{
ConsoleProcessor(String prefix) { ... }
...
}
interface IFilter<T>
{
boolean match(T t);
}
//фильтр по первой буквеclass ByFirstLetter implements IFilter<String>
{
ByFirstLetter(char letter) {...}
...
}
//фильтрует и обрабатывает данные class FilteredGroup<T> implements IGroup<T>
{
private IProcessor<T> processor;
private Filter<T> filter;
public FilteredGroup(IProcessor<T> processor, Filter<T> filter)
{
this.processor = processor;
this.filter = filter;
}
public boolean add(T t)
{
if (filter.match(t))
{
processor.add(t);
return true;
}
return false;
}
public void done()
{
processor.done();
}
}
class СompositeSeqGroup<T> implements IGroup<T>
{
private ArrayList<IGroup<T>> groups;
СompositeSeqGroup(List<IGroup<T>> groups)
{
this.groups = new ArrayList<IGroup<T>>(groups);
}
public boolean add(T t)
{
for (int i = 0; i < groups.size(); i++)
{
if (groups.get(i).add(t))
{
return true;
}
}
return false;
}
public void done()
{
for (int i = 0; i < groups.size(); i++)
{
groups.get(i).done();
}
}
}
И само решение:
public static void main(String[] args)
{
ArrayList<IGroup<String>> groups = new ArrayList<IGroup<String>>();
for (char letter = 'a'; letter <= 'z'; letter++)
{
groups.add(new FilteredGroup<String>(new FileProcessor(Character.toString(letter)), //new ConsoleProcessor(Character.toString(letter)), new ByFirstLetter(letter)));
}
IGroup<String> group = new CompositeSeqGroup<String>(groups)
//Этот код может быть вынесен в класс CompositeSeqGroup, дабы не повторяться...for (int i = 0; i < args.length; i++)
{
group.add(args[i]);
}
group.done();
}
При этом в моих руках остаётся возможность менять политики обработки (как и когда сбрасывать данные в файл или слать в сокет и т.п.), можно заменить CompositeSeqGroup на AsyncCompositeGroup так, что группы не будут ждать друг-друга...
И всё это при минимальных изменениях в коде.
Пытясь же изобразить тоже самое колдовство на haskell — начинаю теряться.
Может кто-нибудь из "гуру" набросать, как будет выглядеть "обобщённое" решение 1-ой задачки в функциональном стиле?
Здравствуйте, NotGonnaGetUs, Вы писали:
NGG>В итоге на свет явлись бы интерфейсы и классы:
NGG>При этом в моих руках остаётся возможность менять политики обработки (как и когда сбрасывать данные в файл или слать в сокет и т.п.), можно заменить CompositeSeqGroup на AsyncCompositeGroup так, что группы не будут ждать друг-друга... NGG>И всё это при минимальных изменениях в коде.
мне всё это напомнило программу сложения 2+2 на 50 строк. на яве, со всеми полагающимися bells and whistles
NGG>Пытясь же изобразить тоже самое колдовство на haskell — начинаю теряться.
NGG>Может кто-нибудь из "гуру" набросать, как будет выглядеть "обобщённое" решение 1-ой задачки в функциональном стиле?
просто реализовываешь sort_and_groupOn и дальше отдаёшь ей какие тебе нужно предикаты, например
main = do readFile "words" >>== words >>== sort_and_groupOn (take 3) >= mapM_ (\list -> writeFile (take 3 (head list)) (unwords list))
это из моей станд. библиотеки:
(>>==) = flip fmap
---------------------------------------------------------------------------------------------------
---- Операции над списками ------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------
-- |Sort and Group list by function result
sort_and_groupOn f = groupOn f . sortOn f
sort_and_groupOn' f = groupOn f . sortOn' f
-- |Sort list by function result (use Schwarznegian transform)
sortOn f = map snd . sortOn' fst . map (keyval f)
-- |Sort list by function result (don't use Schwarznegian transform!)
sortOn' f = sortBy (map2cmp f)
-- |Group list by function result
groupOn f = groupBy (map2eq f)
-- Utility functions for list operations
keyval f x = (f x, x) -- |Return pair containing computed key and original value
map2cmp f x y = (f x) `compare` (f y) -- |Converts "key_func" to "compare_func"
map2eq f x y = (f x) == (f y) -- |Converts "key_func" to "eq_func"
в первую очередь ФП — это мощные средства комбинирования функций (алгоритмов). в ООП такого нет, поэтому традиционный способ описания функторов — это создать класс с виртуальной функцией, которая будет перекрываться в различных реализациях. это неудобно и писанины много. в фп ты просто передаёшь функцию как параметр и можешь легко создавать многоуровневые решения, не боясь запутаться. таким образом, пропадает необходимость описывать монолитный класс, включающий всю необходимую тебе функциональность — порграмма становится более модульной, каждая функция решает ровно одну задачу
NGG>После чего глубоко задумался.
NGG>Задачка, конечно, игрушечная, но что было бы будь это "реальная" задача. Как бы я тогда её решал?
NGG>В итоге на свет явлись бы интерфейсы и классы:
Жжуть.
NGG>Может кто-нибудь из "гуру" набросать, как будет выглядеть "обобщённое" решение 1-ой задачки в функциональном стиле?
Я не гуру и вообще не настоящий сварщик, но. Определим функцию фильтра, которая будет фильтровать ввод,
функцию преобразования — которая будет преобразовывать содержимое файла к тому виду, который нам нужен, и функцию
группировки — соответственно, для группировки, и функцию, которая обрабатывает результаты. И как нибудь так
(на абстрактном языке, но видимо, можно и на хаскелле [а может, даже на окамле]):
input = input_list
filter = filter ( start_with "[:digit:|:letter:]" )
preprocess x = x
by_prefix = ...
output = (* открываем файл и пишем, как-то так: *) iter ( fun x -> output_file (mk_fname) (String.join "\n" (x)) )
do_job_with x = input x >>> filter >>> preprocess >>> group by_prefix >>> output
Здравствуйте, dmz, Вы писали:
dmz>группировки — соответственно, для группировки, и функцию, которая обрабатывает результаты. И как нибудь так dmz>(на абстрактном языке, но видимо, можно и на хаскелле [а может, даже на окамле]):
На Ocamle при желании можно и вариант с интерфейсами и классами повторить
Здравствуйте, BulatZiganshin, Вы писали:
BZ>мне всё это напомнило программу сложения 2+2 на 50 строк. на яве, со всеми полагающимися bells and whistles
Естественно, не зря же я сделал оговорку про игрушечность Это просто иллюстрация подхода: пушкой по воробьям, как говориться.
Но пушкой и воробья и стену кирпичную пробъёшь, а в вот рагаткой стену не пробить.
Мне хочется понять как работает функциональная пушка. Пока я вижу только как мелочёвку всякую щёлкать.
NGG>>Может кто-нибудь из "гуру" набросать, как будет выглядеть "обобщённое" решение 1-ой задачки в функциональном стиле?
BZ>просто реализовываешь sort_and_groupOn и дальше отдаёшь ей какие тебе нужно предикаты, например
BZ>main = do readFile "words" >>== words >>== sort_and_groupOn (take 3) >>= mapM_ (\list -> writeFile (take 3 (head list)) (unwords list))
Типа берётся 3-й символ, а не 1-ый и предполагается, что сортировка стабильная (порядок эквивалентых слов сохраняется)?
Сортировка это дополнительный logN, зачем?
Провероки на диапазон 'a'-'z' уже не нужны?
А как изменится решение, если вместо (take 3) использовать (contains 'a'), (contains 'b')... и т.д.? Т.е. одно и тоже слово может попадать в разные файлы? И как тогда определить имя файла?
Собственно эти вопросы и тревожат.
С одной стороны, когда решение это две строчки, его можно и заново написать, если требования слегка изменятся.
С другой сторы этот подход не маштабируется "на многострочное решение" или особо хитрые ребусы.
Отсюда и мои метания
BZ>в первую очередь ФП — это мощные средства комбинирования функций (алгоритмов). в ООП такого нет, поэтому традиционный способ описания функторов — это создать класс с виртуальной функцией, которая будет перекрываться в различных реализациях. это неудобно и писанины много. в фп ты просто передаёшь функцию как параметр и можешь легко создавать многоуровневые решения, не боясь запутаться.
Угу, в плане "покомбинировать" ФП молодец. Особенно пока можно обойсь "функтором", а не интерфейсом содержащим несколько методов и пока не появились интерфейсы содержащие одинаковые методы, но с разными контрактами...
Про "писанины много" тоже согласен. Раза в два, максимум в три больше. Правда, когда я на с# заворачивал функции высших порядков большой вложенности были проблемы с тем, какие же им имена дать. Очень уже не понятно как называть функцию, которая возвращает функцию, которая возращает функцию делающую то-то и то-то
"не боясь запутаться" — это, как мне кажется, относится только к "чистым" функциям без сайд эффектов и всяких lazy-хитростей. Иначе всё равно буду бояться
BZ>таким образом, пропадает необходимость описывать монолитный класс, включающий всю необходимую тебе функциональность — порграмма становится более модульной, каждая функция решает ровно одну задачу
Допустим, что при использовании функций как первокласных сущностей необходимость описывать монолитный класс пропадает, а разве откуда-то вообще следует необходимость описывать монолитный класс (н-р, при той же оо-декомпозиции)?
Я пока вижу как фп может облегчить мне (местами) жизнь при реализации методов классов.
А как я справлялся бы в функциональном мире с мегабайтами исходных кодов, над которыми работает хотя бы десяток человек, — не представляю, к сожалению...
NGG>Угу, в плане "покомбинировать" ФП молодец. Особенно пока можно обойсь "функтором", а не интерфейсом содержащим несколько методов и пока не появились интерфейсы содержащие одинаковые методы, но с разными контрактами...
import Data.List
lst = [
"dir1\\file1", "dir1\\dir2\\file2", "dir1\\dir3\\file3", "dir4\\file4"]
f lst d = (files, nub [takeWhile (/='\\') x | x <- dirs])
where
ff [] = lst
ff xs = [drop ld x | x <- lst, take ld x == dd]
dd = d ++ "\\"
ld = length dd
(files, dirs) = partition (notElem '\\') $ ff d
Только тут сложность получается не O(N), где N — количество путей в списке, а как минимум O(N*M*К) где M — длинна запрашиваемого пути и К — общее количество файлов начиная с запрашиваемого корня.
Здравствуйте, FR, Вы писали:
NGG>>Угу, в плане "покомбинировать" ФП молодец. Особенно пока можно обойсь "функтором", а не интерфейсом содержащим несколько методов и пока не появились интерфейсы содержащие одинаковые методы, но с разными контрактами...
FR>Так для нескольких функций есть модули, которые в функциональных языках нечто среднее между модулями и объектами из императивных, например в OCaml http://people.cis.ksu.edu/~ab/Courses/505/fall08/htmlman-3.07/manual004.html Кстати функтор в терминологии Ocaml'а http://people.cis.ksu.edu/~ab/Courses/505/fall08/htmlman-3.07/manual004.html#htoc15 манипулирует как раз интерфейсами содержащими несколько методов.
Т.е. это что-то из той же области что и классы в haskell? Механизмы позволяющие опеределить интерфейс для которого можно задать разные реализации.
У меня почему-то стойкое подозрение, что если пустить их в ход, то лаконичности в функциональном решении станет ощутимо меньше, зато гибкости прибудет.
Здравствуйте, Tonal-, Вы писали:
T>Задача (а) как-то так:
как-то всё это сложно
f list dir = list
.$ mapMaybe (stripPrefix (make dir)) -- отберём элементы внутри каталога dir
-- и отрежем от них префикс dir\
.$ partition ('\\' `notElem`) -- разделим на файлы и каталоги
.$ mapSnd (nub . map (takeWhile (/='\\'))) -- удалим дубликаты из списка каталогов
-- Добавить \ к имени каталога, если оно непустое
make "" = ""
make dir = dir++"\\"-- Функция, которая у других авторов обозначается как |>
-- В общем-то, заменяет нам вызов метода класса :)
a.$f = f a
-- Ещё одна функция из моей станд. библиотеки
mapSnd f (a,b) = (a, f b)
T>Только тут сложность получается не O(N), где N — количество путей в списке, а как минимум O(N*M*К) где M — длинна запрашиваемого пути и К — общее количество файлов начиная с запрашиваемого корня.
Здравствуйте, NotGonnaGetUs, Вы писали:
NGG>Т.е. это что-то из той же области что и классы в haskell? Механизмы позволяющие опеределить интерфейс для которого можно задать разные реализации.
Ну по сути да, но кажется поближе к объектам чем в Haskell
NGG>У меня почему-то стойкое подозрение, что если пустить их в ход, то лаконичности в функциональном решении станет ощутимо меньше, зато гибкости прибудет.
Угу, вот только у меня такое же стойкое подозрение, что для этой задачи (смотрю на последнее решение Булата) и для многих других никакие интерфейсы просто не нужны, и результат при этом не менее гибкий.
Здравствуйте, FR, Вы писали:
FR>Угу, вот только у меня такое же стойкое подозрение, что для этой задачи (смотрю на последнее решение Булата) и для многих других никакие интерфейсы просто не нужны, и результат при этом не менее гибкий.
Не соглашусь с последней частью. Я привёл уже вопросы по решению Булата, как раз касательно гибкости... пока ответов нет.
По поводу первой части: я целиком и полностью согласен, что для _этой_ задачи можно обойтись без чего угодно.
Но если решается "реальная" задача (а не игрушечная), имеет смысл обобщить слегка задачу, чтобы прекрыть себе тылы на случай изменений в требованиях. Поэтому я привёл обобщённый вариант нашей игрушечной задачи и его решение в оо-стиле. Это тоже игра Смысл игры в том, чтобы показать как "тупое" ооп может привести к многословному, но достаточно гибкому решению.
Я просил показать, как такой же гибкости достичь методами родными для фя и как-нибудь их озвучить по-возможности. Мне эта тема очень интересна и я не первый раз задаю на rsdn.ru этот глупый вопрос
Здравствуйте, NotGonnaGetUs, Вы писали:
NGG>Здравствуйте, FR, Вы писали:
FR>>Угу, вот только у меня такое же стойкое подозрение, что для этой задачи (смотрю на последнее решение Булата) и для многих других никакие интерфейсы просто не нужны, и результат при этом не менее гибкий.
NGG>Не соглашусь с последней частью. Я привёл уже вопросы по решению Булата, как раз касательно гибкости... пока ответов нет.
Я тоже не гуру, но решение приведу
Повторил точь-в-точь ваше решение.
filterGroup :: [a] -> [(a -> Bool, a -> b)] -> [([a], a -> b)]
filterGroup _ [] = []
filterGroup d (x:xs) = (fst part, snd x) : (filterGroup (snd part) xs) where
part = partition (fst x) d
stdOutput :: (Show a) => String -> a -> IO ()
stdOutput s x = do
putStr $ s ++ ": "
print x
processGroups :: [a] -> [(a -> Bool, a -> b)] -> [[b]]
processGroups d f = map (\x -> map (snd x) (fst x)) $ filterGroup d f
processGroupsIO d f = mapM_ sequence_ $ processGroups d f
filters :: [(String -> Bool, String -> IO ())]
filters = [(('a' `elem`), stdOutput "a"), (('a' `notElem`), stdOutput "not a"), (null, stdOutput "empty")]
theData = ["ala", "dfkja", "jrgh", "", "sejhr", "drt"]
main = let
byFirstLetter c [] = False
byFirstLetter c (x:xs) = x == c
makeFilter :: Char -> (String -> Bool, String -> IO ())
makeFilter c = (byFirstLetter c, stdOutput [c])
groups = map makeFilter ['a'..'z']
in
processGroupsIO theData groups
В ФП ещё и проще получается. Нету лишнего IFilter, так как IGroup всё равно принимает a, а возаращает Bool, т.е. сама является фильтром. Почему у вас FilteredGroup принимает IProcessor тоже неясно. Группировать фильтры в ФП вообще плёвое дело, просто композиция функций.
Здравствуйте, NotGonnaGetUs, Вы писали:
NGG>По поводу первой части: я целиком и полностью согласен, что для _этой_ задачи можно обойтись без чего угодно. NGG>Но если решается "реальная" задача (а не игрушечная), имеет смысл обобщить слегка задачу, чтобы прекрыть себе тылы на случай изменений в требованиях. Поэтому я привёл обобщённый вариант нашей игрушечной задачи и его решение в оо-стиле. Это тоже игра Смысл игры в том, чтобы показать как "тупое" ооп может привести к многословному, но достаточно гибкому решению. NGG>Я просил показать, как такой же гибкости достичь методами родными для фя и как-нибудь их озвучить по-возможности. Мне эта тема очень интересна и я не первый раз задаю на rsdn.ru этот глупый вопрос
Кстати, не соглашусь с реальностью задачи. Дело не в "реальности", а в сложности и потенциальном усложнении при небольшом изменении. Пиши я в ООП, я бы тоже подумал о том, как можно комбинировать фильтры, группы, написал бы кучу интерфейсов, потому что понимал бы, что если внести одно дополнительное требование, то из 50 строк придётся выкинуть 20 и ещё 50 написать, и не дай бог эти интерфейсы используются где-то ещё, придётся и там код менять. Лучше подумать об этом заранее. Тут же было 2(3?) строки, стало 7 (при этом 2 — указание типов функций, 1 — перенос строки). Их и с нуля можно написать, так что заранее напрягаться не стоит.
Вся обобщённая задача сводится к "сгруппировать, выполнить над группами действие". Т.е. тип всей задачи: [a] -> [[a]] -> [[b]].
Первая часть достигается group, если не хватает — groupBy, если не хватает — mySuperGroup. Вторая часть — выполнение действий над группами, map.
Фактически всё, что я сделал, сделав решение таким же, как у Вас, это заменил groupBy на filterGroup и добавил дополнительные данные к группе (само действие), чтобы можно было выполнять разные действия над каждой группой.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>-- Функция, которая у других авторов обозначается как |> BZ>-- В общем-то, заменяет нам вызов метода класса BZ>a.$f = f a
В F# конвейерный оператор обозначается как |>
Насчёи Окамля не знаю, не нашёл такого оператора в описании...
