я часто сталкиваюсь с двумя точками зрения — первая "я знаком с ФП, но оно никакой выгоды в программировании не даёт", и вторая "я знаком с ФП, но так и не научился использовать его для повышения эффективности программирования". собственно, это одно и то же, разница только в том, на кого (ФП или самого человека) возлагается вина за отсутствие результата

и поскольку этот разрыв можно преодолеть, только решая практические задачи, я предлагаю устроить мастер-класс, где опытные фп-программисты будут демонстрировать фп-подход к решению различных практических задач. для того, чтобы можно было ценить насколько вы освоили фп-подход, и оценить его преимущества по сравнению с традиционным, я предлагаю начинать с попыток "учеников" самим решить предлагаемые задачи, и затем демонстрации "учителями" их решений

итак, попробуйте решить эти задачи:

1) есть список слов. надо записать в файл "a" все слова, начинающиеся на букву 'a', в файл "b" — слова на 'b' и т.д. вплоть до z

2) имеется список имён файлов в архиве:

dir1\file1
dir1\dir2\file2
dir1\dir3\file3
dir4\file4

требуется написать функцию, которая по имени каталога возвращает список файлов и подкаталогов в нём, к примеру

f "dir1" = (["file1"], ["dir2","dir3"])

a) сложностью O(кол-во файлов)
б) более эффективную

Здравствуйте, BulatZiganshin, Вы писали:

BZ>я часто сталкиваюсь с двумя точками зрения — первая "я знаком с ФП, но оно никакой выгоды в программировании не даёт", и вторая "я знаком с ФП, но так и не научился использовать его для повышения эффективности программирования". собственно, это одно и то же, разница только в том, на кого (ФП или самого человека) возлагается вина за отсутствие результата

BZ>и поскольку этот разрыв можно преодолеть, только решая практические задачи, я предлагаю устроить мастер-класс, где опытные фп-программисты будут демонстрировать фп-подход к решению различных практических задач. для того, чтобы можно было ценить насколько вы освоили фп-подход, и оценить его преимущества по сравнению с традиционным, я предлагаю начинать с попыток "учеников" самим решить предлагаемые задачи, и затем демонстрации "учителями" их решений

Любопытно. Только у меня несколько другой вариант "ученичества" — уж не знаю, готовы ли "учителя" иметь с этим дело: язык общего назначения с некоторыми функциональными возможностями, и мне интересно, насколько функционален используемый мной подход к задаче.

BZ>итак, попробуйте решить эти задачи:

BZ>1) есть список слов. надо записать в файл "a" все слова, начинающиеся на букву 'a', в файл "b" — слова на 'b' и т.д. вплоть до z

words.
    group_by{|word| word[0]}.
    each{|letter, group| File.open(letter, 'w').write(group.join("\n"))}

BZ>2) имеется список имён файлов в архиве:

BZ>dir1\file1
BZ>dir1\dir2\file2
BZ>dir1\dir3\file3
BZ>dir4\file4

BZ>требуется написать функцию, которая по имени каталога возвращает список файлов и подкаталогов в нём, к примеру

BZ>f "dir1" = (["file1"], ["dir2","dir3"])

BZ>a) сложностью O(кол-во файлов)

def dir_contents(dir)
  pathes.
    select{|path| in_dir?(path, dir)}.
    map{|path| first_path_element(relative_path(path, dir))}.
    uniq.
    partition{|path| is_dir?(path)}
end

# вспомогательные функции могут выглядеть так (а могут, например, работать с объектами файловой системы)
def in_dir?(path, dir)
  path.index(dir) == 0
end

def is_dir?(path)
    path =~ /\\$/
end

def relative_path(path, relative_to)
    path.sub(/^#{relative_to}\\/, '')
end

def first_path_element(path)
    path.sub(/^(\w+?)(?:(\\)\w*)?$/, '\1\2')
end

BZ>б) более эффективную

Здравствуйте, Гест, Вы писали:

Г>Любопытно. Только у меня несколько другой вариант "ученичества" — уж не знаю, готовы ли "учителя" иметь с этим дело: язык общего назначения с некоторыми функциональными возможностями, и мне интересно, насколько функционален используемый мной подход к задаче.

да, более чем, и решения кстати у тебя совершенно fp-шные. смысл тренинга в том, чтобы принести вам пользу, и я тут вижу два "фронта" — сравнить фп и императивные решения на "рабочих" языках, и сравнить удобство фп-программирования на специализированных (хаскелл/окамл/...) и обычных языках. так что пишите так как для вас естественней. в конечном счёте, я надеюсь, вы получите навык использования фп-языков на все 100, и навык использования фп-подходов к решению задач в обычных языках тоже

BZ>>б) более эффективную

Г>

имеется в виду разумеется построение промежуточной структуры данных y, которое позволит далее вычислять dir file y за время меньше O(N)


3-я задача: есть функция сжатия compress :: String -> String. ей на вход передаётся строка (или буфер и его размер — это непринципиально), а она возвращает сжатые данные. и есть аналогичная функция decompress. при этом они однопоточные. а у нас 4-процессорная машина. соответственно, нужно написать программу, читающую входные данные мегабайтными блоками, и упаковывающую "в 4 руки", и к ней программу распаковки

Здравствуйте, BulatZiganshin, Вы писали:

BZ>>>б) более эффективную

Г>>

BZ>имеется в виду разумеется построение промежуточной структуры данных y, которое позволит далее вычислять dir file y за время меньше O(N)

А, понял. Я подумал про промежуточную структуру, но решил что это выходит за рамки задачи.
Что приходит в голову сходу — это, собственно, сразу построить дерево папок:

        |dir2 => file2
dir1 => |dir3 => file3
        |file1
dir4 => file4

Тогда сложность ее будет, если не ошибаюсь, O(M), где M — кол-во папок верхнего уровня.
Типа так:

dirlist = pathes.
  group_by{|path| first_path_element(path)}.                        #складываем по папкам
  map{|dir, group| [dir, group.map{|path| relative(path, dir)}]} #откусываем имя папки, в которую положили

def dir_contents(dir)
  res = dirlist.detect{|d, path| d == dir}
  res && res.last || [] #last - в смысле, из массива [папка, [содержимое папки]]
end

Более разумный вариант — превратить dirlist в словарь (папка — содержимое). Тогда сложность поиска, естественно, определяется сложностью поиска по словарю в целеовм языке.

dirlist_hash = dirlist.to_hash

def dir_contents(dir)
  dirlist_hash[dir]
end

наверное, можно как-то умнее.


BZ>3-я задача: есть функция сжатия compress :: String -> String. ей на вход передаётся строка (или буфер и его размер — это непринципиально), а она возвращает сжатые данные. и есть аналогичная функция decompress. при этом они однопоточные. а у нас 4-процессорная машина. соответственно, нужно написать программу, читающую входные данные мегабайтными блоками, и упаковывающую "в 4 руки", и к ней программу распаковки

Мммм...

AMOUNT = 1024 * 1024

#исхожу из того, что stream.read сдвигает указатель начала входного потока
def compress4(stream)
  stream.
    #превращаем поток в массив массивов из 4х элементов по 1 Мб
    unfold{|stream| stream.empty? ? nil : [(1..4).map{stream.read(AMOUNT)}, stream]}. 
    #сжимаем, исходя из того, что map у нас достаточно умен для распараллеливания ;)
    #и сразу склеиваем 4 сжатых кусочка в 1
    map{|four_chunks| four_chunks.map{|chunk| compress(chunk)}.join}.
    join        #...и склеиваем все
end

Тут, правда, наверное, надо оговорить, что простое "склеивание" сжатых кусочков может дать абсолютно некорректный результат, в зависимости от алгоритмов сжатия

Разжатие не пишу — кажется, будет абсолютно то же самое, только compress надо заменить на decompress

Здравствуйте, Гест, Вы писали:

Г>А, понял. Я подумал про промежуточную структуру, но решил что это выходит за рамки задачи.

ну понятно же, что меньше O(N) на самом списке не получишь

Г>Что приходит в голову сходу — это, собственно, сразу построить дерево папок:
Г>

Г>        |dir2 => file2
Г>dir1 => |dir3 => file3
Г>        |file1
Г>dir4 => file4
Г>

Г>Тогда сложность ее будет, если не ошибаюсь, O(M), где M — кол-во папок верхнего уровня.
Г>Типа так:
Г>

Г>dirlist = pathes.
Г>  group_by{|path| first_path_element(path)}.                        #складываем по папкам
Г>  map{|dir, group| [dir, group.map{|path| relative(path, dir)}]} #откусываем имя папки, в которую положили

результат будет что-то типа такого:

[("dir1", ["dir2/file2", "dir3/file3", "file1"]), ...)


Г>  res && res.last || [] #last - в смысле, из массива [папка, [содержимое папки]]

а не лучше писать "res? res.last : []" ?  кстати path во множ. числе тоже вроде paths :)

Г>Более разумный вариант - превратить dirlist в словарь (папка - содержимое). Тогда сложность поиска, естественно, определяется сложностью поиска по словарю в целеовм языке.

ага. но для этого надо построить другой dirlist, нежели дерево

Г>#исхожу из того, что stream.read сдвигает указатель начала входного потока
Г>def compress4(stream)
Г>  stream.
Г>    #превращаем поток в массив массивов из 4х элементов по 1 Мб
Г>    unfold{|stream| stream.empty? ? nil : [(1..4).map{stream.read(AMOUNT)}, stream]}. 
Г>    #сжимаем, исходя из того, что map у нас достаточно умен для распараллеливания ;)
Г>    #и сразу склеиваем 4 сжатых кусочка в 1
Г>    map{|four_chunks| four_chunks.map{|chunk| compress(chunk)}.join}.
Г>    join        #...и склеиваем все
Г>end
Г>

вот и напишите этот map в общем, это была задача именно на высокоуровневый подход к многозадачности. ваше решение мне нравится — именно в fp-шном стиле декомпозиция задачи на отдельные элементы плюс подход в стиле "обработка потока данных"

Здравствуйте, BulatZiganshin, Вы писали:

Г>>Типа так:
Г>>

Г>>dirlist = pathes.
Г>>  group_by{|path| first_path_element(path)}.                        #складываем по папкам
Г>>  map{|dir, group| [dir, group.map{|path| relative(path, dir)}]} #откусываем имя папки, в которую положили

BZ>результат будет что-то типа такого:

BZ>[("dir1", ["dir2/file2", "dir3/file3", "file1"]), ...)

Ну да.

Г>>  res && res.last || [] #last - в смысле, из массива [папка, [содержимое папки]]

BZ>а не лучше писать "res? res.last : []" ?  кстати path во множ. числе тоже вроде paths :)

Угу.

Г>>Более разумный вариант - превратить dirlist в словарь (папка - содержимое). Тогда сложность поиска, естественно, определяется сложностью поиска по словарю в целеовм языке.

BZ>ага. но для этого надо построить другой dirlist, нежели дерево

? почему другой? вот прямо этот [ [dir, contents], ...] отлично превращается в словарь.

Г>>#исхожу из того, что stream.read сдвигает указатель начала входного потока
Г>>def compress4(stream)
Г>>  stream.
Г>>    #превращаем поток в массив массивов из 4х элементов по 1 Мб
Г>>    unfold{|stream| stream.empty? ? nil : [(1..4).map{stream.read(AMOUNT)}, stream]}. 
Г>>    #сжимаем, исходя из того, что map у нас достаточно умен для распараллеливания ;)
Г>>    #и сразу склеиваем 4 сжатых кусочка в 1
Г>>    map{|four_chunks| four_chunks.map{|chunk| compress(chunk)}.join}.
Г>>    join        #...и склеиваем все
Г>>end
Г>>

BZ>вот и напишите этот map

Ой нет. Эт я даже не представляю, с чего начинать. В смысле, если писать на Рубях, нужна видимо какая-то библиотека для параллельности, а я такими вопросами не задавался

Здравствуйте, Гест, Вы писали:

BZ>>результат будет что-то типа такого:

BZ>>[("dir1", ["dir2/file2", "dir3/file3", "file1"]), ...)

Г>Ну да.

нам нужно, чтобы
1) f "dir1" возвращало "file1", "dir2", "dir3" вне зависмости от кол-ва фалйов в dir2/dir3
2) f "dir1/dir2" возвращало "file2"

Здравствуйте, BulatZiganshin, Вы писали:

BZ> итак, попробуйте решить эти задачи:
BZ> 1) есть список слов. надо записать в файл "a" все слова, начинающиеся на букву 'a', в файл "b" — слова на 'b' и т.д. вплоть до z

import Char
import List

main = do
    ls <- readFile "word.txt"

    let fs = words ls
          |> sortBy  (\(x:_) (y:_) -> toLower x `compare` toLower y)
          |> groupBy (\(x:_) (y:_) -> x == y)
          |> filter  (\((x:_):_)   -> isAlpha x)

    mapM_ (\f@((c:_):_) -> writeFile [c] $ unlines f) fs


infixl 0 |>
x |> f = f x

BZ> 2) имеется список имён файлов в архиве:
BZ> dir1\file1
BZ> dir1\dir2\file2
BZ> dir1\dir3\file3
BZ> dir4\file4
BZ> требуется написать функцию, которая по имени каталога возвращает список файлов и подкаталогов в нём, к примеру
BZ> f "dir1" = (["file1"], ["dir2","dir3"])

Не совсем понятно условие. Должен ли просмотр идти по дереву каталогов и для запроса f "dir1" выдать (["file2"], []) или же можно ограничиться просмотром имён каталогов верхнего уровня?
Если второе, то вот:

import List

dirs = [ "dir1\\file1"
       , "dir1\\dir2\\file2"
       , "dir1\\dir3\\file3"
       , "dir4\\file4"
       ]

slash2tab c = if c == '\\' then "\\\t" else [c]

dirs' = map (\d -> words $ (concat $ map slash2tab d)) dirs

f'a dir = filter (\(d:_) -> init d == dir) dirs'
       |> map tail
       |> (\xs -> ( concat $  filter (\(x:_) -> last x /= '\\') xs
                  , filter (\(x:_) -> last x == '\\') xs
                    |> map (init.head)))


infixl 0 |>
x |> f = f x

PS. За изменениями условия задачи прямо не поспеешь... :о(

Здравствуйте, BulatZiganshin, Вы писали:

BZ>имеется в виду разумеется построение промежуточной структуры данных y, которое позволит далее вычислять dir file y за время меньше O(N)

Так у преобразования в такую структуру сложность всё равно O(кол-во файлов)...

Здравствуйте, geniepro, Вы писали:

> ... и для запроса f "dir1" выдать (["file2"], []) ...

имел в виду "для запроса f "dir2" выдать (["file2"], [])", впрочем, похоже, уже не важно... :о)

Здравствуйте, BulatZiganshin, Вы писали:



BZ>и поскольку этот разрыв можно преодолеть, только решая практические задачи, я предлагаю устроить мастер-класс, где опытные фп-программисты будут демонстрировать фп-подход к решению различных практических задач. для того, чтобы можно было ценить насколько вы освоили фп-подход, и оценить его преимущества по сравнению с традиционным, я предлагаю начинать с попыток "учеников" самим решить предлагаемые задачи, и затем демонстрации "учителями" их решений

"Решение практических задач" мне кажется — это составление программы, которая делает что-то полезное. Поэтому предлагаемые задачи не кажутся практическими. Скорее они всего лишь демонстрируют, что на каком-то языке ФП можно записать в 5 строчках то, что в простом Си заняло бы 10 строчек. Естественно, что это не доказывает преимущество ФП, даже если считать строчки — в простой задаче эта разница просто не имеет значения,а стоит задаче стать немного нетривиальной, как обнаружится слабость стандартной библиотеки (в терминологии Си) языков ФП по сравнению с нормальными, что плохо повлияет на количество строчек.
Кстати, в Си решение обеих задач тривиально (хотя код для поиска файлов зависит от платформы). Если функциональщикам эти задачи кажутся нетривиальными, то это тоже заставляет усомниться в полезности ФП.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>2) имеется список имён файлов в архиве:

в этой задаче я подразумевал много вещей, которые оказались неочевидны. итак, уточнённая формулировка:

имеется список имён файлов в архиве:

dir1\file1
dir1\dir2\file2
dir1\dir3\file3
dir4\file4

мы пишем программу типа far/tc, которая позволит ходить по каталогам такого архива. для этого нужно написать функцию, возвращающую список файлов/каталогов в любом каталоге:

f ""          = ([],        ["dir1","dir4"])
f "dir1"      = (["file1"], ["dir2","dir3"])
f "dir1\dir2" = (["file2"], [])

a) сложностью O(кол-во файлов), манипулирующую непосредственно с исходным списком
б) более эффективную, манипулирующую промежуточной структурой данных, которую мы строим из списка. т.е. в этом случае мы при входе в архив строим некое эффективное представление его каталога, которое позволяет нам в дальнейшем быстро ходить по архиву

P>Кстати, в Си решение обеих задач тривиально (хотя код для поиска файлов зависит от платформы).

Ну так можно привести тривиальное сишное решение хотя бы первой задачи?

P>а стоит задаче стать немного нетривиальной, как обнаружится слабость стандартной библиотеки (в терминологии Си) языков ФП по сравнению с нормальными, P>что плохо повлияет на количество строчек.

Про слабость стандартной библиотеки, например, хаскелла или окамла — это откуда мысль? Может быть, вы ее подтвердите?

Решение первой задачи для окамла — как-то несколько многословно. Если кто-то знает окамл — может найдется лучшее решение?

open Std
open ExtList.List
open ExtString

(* group -  нигде нет *)
let rec group f l = match l with
     | x::xs -> let m,n = partition (fun y -> (f x) = (f y)) xs in [x :: m] @ group f n
     | []    -> []

let words = 
    (* isAlpha тоже нигде нет *)
    let filt  x = let good = function 
        | 'a' .. 'z' | 'A' .. 'Z' -> true
        | _                       -> false
        in (filter (fun a -> a <> "" &&  good a.[0]) x) in
    let read    = input_list stdin
    in group (fun x -> x.[0]) (filt read)

let _ = iter ( fun x -> output_file (String.sub (hd x) 0 1) (String.join "\n" (x)) ) words

dmz@x200:~/prj/ocaml/shit$ wc -l ./filez 
67406 ./filez
dmz@x200:~/prj/ocaml/shit$ time cat filez  | ./a.out 

real    0m0.201s
user    0m0.176s
sys    0m0.028s

Мой вариант первой задачи на Окамле. Не слишком красиво, зато линейная сложность (никаких сортировок).

let (|>) x f = f x;;

let words = ["Not"; "so"; "long"; "list"; "of"; "9-10"; "not"; "so"; "weird"; "words"];;

let idx s =
  if s<>"" then
    if s.[0]>='A' && s.[0]<='Z' then Some( (int_of_char s.[0]) - 65 ) else
    if s.[0]>='a' && s.[0]<='z' then Some( (int_of_char s.[0]) - 97 ) else None
  else None;;
  
let group lst =
  let a = Array.make 26 [] in
  List.iter (fun s-> match idx s with Some i -> a.(i) <- s::a.(i) | None -> ()) lst; a;;
  
let write =
  Array.iteri (fun i lst -> if lst <> [] then 
    Std.output_file ~filename:(i+97 |> char_of_int |> Std.string_of_char) 
                    ~text:(String.concat "\n" (List.rev lst)));;

words |> group |> write;;

Здравствуйте, dmz, Вы писали:

dmz>Ну так можно привести тривиальное сишное решение хотя бы первой задачи?

На плюсах.
Вариант №1. Do not optimize prematurely...

vector<string> words;

for(int i = 0, end = words.size(); i != end; ++i)
{
   ofstream(words[i].substr(0,1).c_str(), ios::app) << words[i] << ' ';
}

Вариант №2.

ofstream* ofs[26];

for(char c = 'a'; c <= 'z'; ++c)
{
    ofs[c - 'a'] =  new ofstream(string(1, c).c_str());
}

vector<string> words;

for(int i = 0, end = words.size(); i != end; ++i)
{
    *ofs[words[i][0] - 'a'] << words[i] << ' ';
}

Здравствуйте, Basil B, Вы писали:

dmz>>Ну так можно привести тривиальное сишное решение хотя бы первой задачи?

отлично. а теперь условия задачи меняются — имя файла определяется первыми трёмя буквами слова. открывать файл для записи каждого слова заново — очень накладно. ваши действия?

DM>Мой вариант первой задачи на Окамле. Не слишком красиво, зато линейная сложность (никаких сортировок).

Если писать деструктивно, то можно так (чуть меньше кода):

open Std
open ExtList.List
open ExtString
open ExtHashtbl


let group l = 
    let hsh =  Hashtbl.create 1000 in
    let k s = if String.length s > 0 && ((s.[0] >= 'A' && s.[0] <= 'Z') || (s.[0] >= 'a' && s.[0] <= 'z'))
              then String.sub s 0 1 else "" in
    let step x = let key = k x in
                 if not (Hashtbl.exists hsh key) then Hashtbl.add hsh key (x::[])
                 else let item = Hashtbl.find hsh key in Hashtbl.replace hsh key (x::item)
    in Enum.iter step l ; hsh

let _ = 
    let hsh = group (input_lines stdin) in
    Enum.iter ( fun x -> if x <> "" then output_file x (String.join "\n" (Hashtbl.find hsh x) )) (Hashtbl.keys hsh)

dmz>>Ну так можно привести тривиальное сишное решение хотя бы первой задачи?

BB>Вариант №1. Do not optimize prematurely...
BB>Вариант №2.

Ща тут будет дуэль на мясорубках, так что давайте по-честному.
1) Файлы проверять на то, что бы имя было из букв (сказано же, что из букв?)
2) Читать таки давайте из консоли, а то смысл зашивать список в программе?
3) Писать весь код — что бы можно было скомпилить и запустить — инклуды, main
4) Память за собой чистить

Здравствуйте, dmz, Вы писали:

dmz>Ща тут будет дуэль на мясорубках, так что давайте по-честному.

оно кому нужно??? задача стоит в сдвиге парадигмы мышления, и насильно мил не будешь

BZ>отлично. а теперь условия задачи меняются — имя файла определяется первыми трёмя буквами слова. открывать файл для записи каждого слова заново — очень накладно. ваши действия?

Ну я и так повторно файл не открываю (хотя может надо — тогда отыграем строчек у ++ )

open Std
open ExtList.List
open ExtString

(* group -  нигде нет. тормозно, но можно переписать на хэшах - будет быстро. *)
let rec group f l = match l with
     | x::xs -> let m,n = partition (fun y -> (f x) = (f y)) xs in [x :: m] @ group f n
     | []    -> []

let dump_words = 
    let good c = match c with 
        | 'A' .. 'Z' -> c
        | 'a' .. 'z' -> c
        | _ -> '_' in
    let sanitize x = String.map good x in
    let fname x  = sanitize (if String.length x >= 3 then String.sub x 0 3 else x) in
    let read     = input_list stdin in
    let filt l   = filter (fun s -> s <> "") l in
    let dump = iter ( fun x -> output_file (fname (hd x)) (String.join "\n" (x)) ) 
    in dump (group fname (filt read))

let _ = dump_words