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

Так весело же. И потом — ФП же должно уменьшать количество писанины или нет? А так же тестирования и отладки.

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

#include <vector>
#include <iostream>

using namespace std;

int main(int,char**)
{
    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] << ' ';
    }

}

Все-таки, допишите сюда, пожалуйста, кто-нибудь, чтение вордлиста из stdin — мне просто интересно, во что
выльется повторное открытие файла. И что-то надо сделать, что бы компилятор не ругался:

dmz@x200:~/prj/ocaml/shit$ g++ ./t10cc.cc 
./t10cc.cc: In function ‘int main(int, char**)’:
./t10cc.cc:12: error: invalid use of incomplete type ‘struct std::ofstream’
/usr/include/c++/4.3/iosfwd:89: error: declaration of ‘struct std::ofstream’

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

Что будет, если в списке файлов попадется ' ' ? . ? .. ? CON ? PRN ?

BB>[ccode]

BB>ofstream* ofs[26];
...
BB> ofs[c — 'a'] = new ofstream(string(1, c).c_str());

Деструкторы не сработают — файлы не закроются? В приведенном решении на окамле
все ужимки с группировкой были для того, что бы избежать открытий и закрытий файлов —
файл пишется одной атомарной функцией. Если файлы открывать, и не заботиться о
закрытии — то писанины (на окамле) сильно убавится — например, можно будет просто писать за один
проход. Причем при выходе мусор должен подсобраться, и файлы все таки закроются. А вот в ++ при таком
выделении — закроются?

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

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

Я пас.

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

BB>Я пас.

Тогда фиксируем результат, что если привести с++ — ный код в рабочее состояние — то это будет уже не две строчки, а как
минимум не меньше, чем в ФП-подходе? А вот если начать налагать доп. условия, типа имя файла -> первые три буквы,
или, например, попросить писать в каждый файл только уникальные строки — ++ начинает сливать?

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

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

Если в лоб решать, то:

vector<string> words;

sort(words.begin(), words.end(), Less3);

vector<string>::iterator upper, cur = words.begin(), end = words.end();

while(cur != end)
{
    upper = upper_bound(cur, end, *cur, Less3);
    
    ofstream ofs(cur->substr(0,3).c_str());

    while(cur != upper)
    {
        ofs << *cur++ << ' ';
    }
}

А Less3 определим так:

bool Less3(std::string const& l, std::string const& r)
{
  return l.substr(0,3) < r.substr(0, 3);
}

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

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

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

Я был нетрезв.

module Enumerable
    def parallel_map(&block)
        results = []
        threads = self.to_enum(:each_with_index).
            map{|obj, i| Thread.new{results[i] = block.call(obj)} }.each{|t| t.join}
        
        results
    end
end

#тестируем
r = [1,2,3,4,5].parallel_map{|i| p Thread.current; i+5}
p r

выводит:

#<Thread:0x297db6c run>
#<Thread:0x297da18 run>
#<Thread:0x297d900 run>
#<Thread:0x297d7e8 run>
#<Thread:0x297d6d0 run>
[6, 7, 8, 9, 10]

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

Впрочем, в Ruby 1.9 они уже нативные.

ЗЫ: про ошибку в задаче с папками уже понял, как ее исправить — тоже очевидно.

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

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

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

Это еще вопрос, как получить O(N) для построения словаря dir1 -> [sudir1, ...] именно из списка вида

/dir1/subdir1/subsubdir1
/dir1/subdir2/subsubdir2
...

(а не с самой файловой системы или еще откуда)

ведь нам для каждого каталога уровня N надо перечислить все каталоги уровня N+1.
получать-то потом можно за константу, не в том вопрос. Это точно решается в таком виде именно за O(N) ?

Тупо в лоб как-то так:

open Std
open ExtList.List
open ExtString

let delim = "/"

let spath s = filter (fun x -> x <> "") (String.nsplit s delim)

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 gen_p p =
    let path = spath p in
    let ml = length path 
    in let rec ggen l path  = 
            if l < ml then (String.join delim (take l path), nth path (l)) :: ggen (l+1) path
            else (String.join delim (take l path), "")::[]
    in ggen 1 path


let gen_all l = map ( fun x -> (fst (hd x), map snd x )) (group fst (fold_left (@) [] (map gen_p l)))

(* можно хэш построить,  но лень -  суть понятна *)
let _ = List.accos "home" gen_all (input_list stdin)

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

dmz> А вот если начать налагать доп. условия, типа имя файла -> первые три буквы,
dmz>или, например, попросить писать в каждый файл только уникальные строки — ++ начинает сливать?

Давайте не будем превращать тред в очередное меряние языками. Исходный замысел Булата был совсем другим, и он намного интереснее.

DM>Давайте не будем превращать тред в очередное меряние языками. Исходный замысел Булата был совсем другим, и он намного интереснее.

Он про сдвигание парадигмы. Но парадигму надо двигать ради чего-то. Лично у меня она подвинулась, когда некоторые сложные задачи просто перестали делаться, при пересмотре подхода в сторону фп, рекурсии и отсутствия мутабельных данных — решились быстро и просто. Но это в топике не покажешь — и вообще это сложно-показуемая вещь. Всегда ведь можно упереться и сделать на чем угодно.

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

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

Кстати, этот вариант можно еще упростить, если вспомнить, что Hashtbl.add сам добавляет значение в список, а Hashtbl.find_all выдает весь список.

DM>Кстати, этот вариант можно еще упростить, если вспомнить, что Hashtbl.add сам добавляет значение в список, а Hashtbl.find_all выдает весь список.

Что-то он мне вообще не нравится. Надо написать на чем-то (пусть грязном) group, куда-то его запрятать, и дальше писать чисто. Кстати, хэштейбл идет ноздря в ноздрю с решением на массивах, даже иногда быстрее (правда в пределах погрешности). Так что стараться сделать максимально грязно не стоит — достаточно написать group с изменяемым состоянием и все.

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

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

Спешл фор dmz компилирующийся код.

#include <string>
#include <fstream>
#include <map>

typedef std::map<std::string, std::string> StringToString;

int main(int /*argc*/, char* /*argv[]*/)
{
    using namespace std;

    StringToString m;

    ifstream in("corncob_lowercase.txt"); // http://www.mieliestronk.com/corncob_lowercase.zip

    string temp;    

    while(in >> temp)
        m[temp.substr(0,3)].append(temp).append("\n");

    for(StringToString::iterator i = m.begin(), end = m.end(); i != end; ++i)
    {
        ofstream out(i->first.c_str());
        out << i->second;
    }

    return 0;
}

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

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

Отличные задачки, для девятиклассников. Если хочется реально продемонстрировать мастер-класс, возьми какую-нибудь более реальную задачу, результатом которой будет законченный проект. Понятное дело не слишком крупный, но и не слишком простой. Ну там, начни с архитектуры приложения, покажи как делается функциональная декомпозиция (проектирование), сравни с тем, как это выглядело бы в ООП. Где там реальный выигрыш, в чем он проявляется. Дальше реализация, тоже с указаниями и сравнениями с ООП подходом.

А вот какую задачку взять, это вопрос...

Y>Отличные задачки, для девятиклассников.

Нормальные задачи. Похожи на куски задач, которые регулярно возникают.

Y>Если хочется реально продемонстрировать мастер-класс, возьми какую-нибудь более реальную задачу,
Y>результатом которой будет законченный проект. Понятное дело не слишком крупный, но и не слишком простой.

Ну вот не вопрос. Компилятор из луа-подобного языка в байткод для условной стековой VM. Или вот — взять файлы с SQL описанием таблиц
(с констрейнтами), распарсить, сгенерировать код для доступа к базе, а так же валидаторы форм (на основе констрейнтов).

Небольшие проекты, совсем. Первый — всего сотен пять строк. Никто не хочет порешать?
Булат дал неплохие примеры, которые можно не напрягаясь поделать, по фану. Что-то сильно более сложное — никто делать не будет.

Y>Где там реальный выигрыш, в чем он проявляется. Дальше реализация, тоже с указаниями и сравнениями с ООП подходом.

Сравнение ФП vs ОО смысла не имеет, т.к. программа в функциональном стиле может также являться в каком-то смысле ОО.
Сравнивать имеет смысл императивный vs декларативный подход.

Y>А вот какую задачку взять, это вопрос...

Можно взять генератор кодов хаффмана. Прочитать байты из STDIN, построить словарь, сдампить словарь + упакованные данные в STDOUT.

dmz>Можно взять генератор кодов хаффмана. Прочитать байты из STDIN, построить словарь, сдампить словарь + упакованные данные в STDOUT.

На питоне генератор кодов пишется строки в три, что ли.

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

dmz>На питоне генератор кодов пишется строки в три, что ли.

А можно посмотреть?

dmz>Деструкторы не сработают — файлы не закроются? В приведенном решении на окамле
dmz>все ужимки с группировкой были для того, что бы избежать открытий и закрытий файлов —
dmz>файл пишется одной атомарной функцией. Если файлы открывать, и не заботиться о
dmz>закрытии — то писанины (на окамле) сильно убавится — например, можно будет просто писать за один
dmz>проход.

Чтобы файлы закрывались (в том числе при исключениях) есть RAII (так в С++ называют scoped resource management) — причем в окамле его сделать даже легче, чем в С++, поскольку есть ФВП.

how to do RAII in higher-order languages
Пример на Scala

Вот пример на на диалекте луа:

-- (* RAII facilities *)
fun unwind_protect(thunk, cleanup) ->
  local ok, result = pcall(thunk)
  if cleanup then cleanup() end
  if not ok then error(result,0) else return res end
end

fun with_open_file(path,mode) ->
  fun (body) ->
    local file = assert(io.open(path,mode))
    return unwind_protect(fun()-> body(file) end, =>file:close())
  end
end

fun with_file_list() ->
  fun (body) ->
    local flist = {}
    return unwind_protect(
      fun()-> body(flist) end,
      fun()-> 
        for _,file in pairs(flist) do file:close() end 
      end)
  end
end

Тогда задание 1 можно записать вот так:

-- (* '$' работает как в Haskell *)
-- (* '=>' делает thunk из выражения справа: '=> expr' тоже самое, что: 'fun() -> expr end' *)
print$pcall$=>
with_open_file("words.txt","rb")$fun (infile) ->
  local words = infile:read("*a")
  return with_file_list()$fun (filelist) ->
    for word, first in words:gmatch"((%a)%a*)" do
      filelist[first] or= assert(io.open(first..".txt","wb"))
      filelist[first]:write(word,'\n')
    end
  end
end

bash$ hluago wordlist.hlua
true    nil
bash$ tail -n 3 j.txt
juxtaposition
juxtapositional
juxtapositions

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

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

dmz>>На питоне генератор кодов пишется строки в три, что ли.

DM>А можно посмотреть?

Память подвела, поболе получается (отсюда):

import heapq

def makeHuffTree(symbolTupleList):
    trees = list(symbolTupleList)
    heapq.heapify(trees)
    while len(trees) > 1:
        childR, childL = heapq.heappop(trees), heapq.heappop(trees)
        parent = (childL[0] + childR[0], childL, childR)
        heapq.heappush(trees, parent)
    return trees[0]

и это ему надо еще таблицу вероятностей символов подсунуть.

Z>Чтобы файлы закрывались (в том числе при исключениях) есть RAII (так в С++ называют scoped resource management)

не вопрос, только в конструкции вида:

ofstream *handles[26]
...
for( ... ) 
{
   handles[i] = new ofstream(...);
}
...

предложенной в топике, хэнлды не закроются. Наверное, можно было впихнуть какие-нибудь auto_ptr-ы вместо голых указателей — но это уже не ко мне. ++ забыл напрочь и как-то не тянет вспоминать. Мне вот интересно, почему в окамле нет встроенных функций group и т.п.