Re[8]: JRuby, RubyCLR, IronPython - зачем?
От: Mirrorer  
Дата: 22.11.06 13:13
Оценка: +1 :)
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

M>>Всего лишь рекурсивный поиск с откатом, говоришь ? Трудно представить существенно разные решения говоришь ?

M>>Красота!
Автор: Lazy Cjow Rhrr
Дата: 06.12.05


LCR>Ну, прищучил... Но! Эта "красота" — рекурсивный поиск с откатом. Рекурсия хвостовая, и подбор-откат делается в параметрах.

Ну это да, идея больше относилась к существенно разным решениям. То есть идея то одна, а реализация в "Красоте" — ухх!


LCR>Тем не менее ты прав , не все решения упираются в рекурсивный поиск. Если подумать, можно ещё способы напридумывать.

Угу. Вывести какую-нибудь формулу для получения готового решения допустим, и записать ее в 1 строчку на J
... << RSDN@Home 1.2.0 Deep Purple — Maybe I'm A Leo >>
Re[6]: Требуются примеры использования first class function
От: Кодт Россия  
Дата: 22.11.06 13:14
Оценка:
Здравствуйте, Трурль, Вы писали:

PA>>outside r = \p -> not (p `inRegion` r)
PA>>x /\ y = \p -> (p `inRegion` x) && (p `inRegion` y)
PA>>x \/ y = \p -> (p `inRegion` x) || (p `inRegion` y)

Т>вот этот кусок можно было бы записать и попроще
Т>outside  = not
Т>(/\) = (&&)
Т>(\/) = (||)


Нет.
inRegion {- x  p -} = ($) -- x $ p = p x
-- поэтому ниже мы его выплавим

outside {- x   p -} = f_gx    (not) {- x   p -}
(/\)    {- x y p -} = f_gx_hx (&&)  {- x y p -}
(\/)    {- x y p -} = f_gx_hx (||)  {- x y p -}

-- где комбинаторы
f_gx    f g x   = f (g x)       -- хорошо известный (.)
f_gx_hx f g h x = f (g x) (h x) -- лень выводить (в базисе Прелюдии будет выглядеть страшно)
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[7]: Требуются примеры использования first class function
От: Programmierer AG  
Дата: 22.11.06 13:36
Оценка:
Кодт wrote:
>
> inRegion {- x  p -} = ($) -- x $ p = p x
> -- поэтому ниже мы его выплавим
-- на самом деле inRegion = flip ($)
>
Posted via RSDN NNTP Server 2.0
Re[7]: Требуются примеры использования first class function
От: Трурль  
Дата: 22.11.06 14:49
Оценка: 99 (3)
Здравствуйте, Кодт, Вы писали:

К>Нет.



К>
К>inRegion {- x  p -} = ($) -- x $ p = p x
К>-- поэтому ниже мы его выплавим

К>outside {- x   p -} = f_gx    (not) {- x   p -}
К>(/\)    {- x y p -} = f_gx_hx (&&)  {- x y p -}
К>(\/)    {- x y p -} = f_gx_hx (||)  {- x y p -}

К>-- где комбинаторы
К>f_gx    f g x   = f (g x)       -- хорошо известный (.)
К>f_gx_hx f g h x = f (g x) (h x) -- лень выводить (в базисе Прелюдии будет выглядеть страшно)
К>

Вот примерно то же собирался написать.
В качестве f_gx_hx (aka lift2 aka fork ) можно применить liftM2. Только надо обьяснить Хаскелю, что (a->) — тоже монада.
instance Monad ((->) a) where
    return  a = \x-> a
    (>>=) f g  = \x-> g (f x) x

lift2 :: (a -> b -> c) -> (d -> a) -> (d -> b) -> d -> c 
lift2 = liftM2 

lift1 = (.)

outside = lift1 not
(/\) =  lift2 (&&)
(\/) =  lift2 (||)
Re[5]: Требуются примеры использования first class function
От: PhantomIvan  
Дата: 22.11.06 15:19
Оценка:
PI>>тут наверно, как в императивщине — смотришь в чужой код, иногда думаешь, о! интересный оборот...

VD>Вот и нужны такие места. Но так чтобы примеры не были надумаными, были понятны большиству и при этом демонстрировали реальные приемущества.


то есть насколько "не надуманные"? настолько, чтобы действительно реальные применения были?

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

попробуем пример из интеграции: вот функция в составе тест-пакета, тестирует фичу "find references" (нахождение в коде всех ссылок на некоторую переменную, метод, функцию, т.д.)

public FindUsages(line: string, testCase : int, declaration : Location, starter : string) : bool
{
    в тестовом сорце встречаются строки вида 
        mutable acquired = false; // definition {2} acquired     (явное указание объявлений в комментах)
    и строки вида
        acquired = true;  // usage {2}


    выявляем, что ищем
    def name = starter.Substring(starter.IndexOf('}') + 1).Trim();
    def position = line.IndexOf(name);
    def location = Location(declaration.File, declaration.Line, position, declaration.Line, position + name.Length);
    WriteLine($"\nSearching for usages of '$name' (test case: $testCase, location: $location)... ");
    выявили эн вхождений, для которых будем тестировать find references пакета интеграции
    def shouldFindRing = MakeUsage(line, declaration, name, starter) ::
        ScanSources(checkPhrase, testCase).Map((line, _, location, _) => MakeUsage(line, location, name, checkPhrase));
    Write($"\n Should find $(shouldFindRing.Length) usages... ");
    
    для каждого вхождения имитируем клик на нём юзером, и выбор команды find references
    получается список из эн списков, каждый из которых должен быть равен другому
    (действие команды не зависит от того, на каком вхождении кликнул юзер)
    def foundMultiple =
        shouldFindRing.Map(goto =>
        {
            def location = goto.Location;
            def shift = if (name.Length > 1) 1 else 0;
            TheEngine.Project.GetUsages(location.File, location.Line, location.Column + shift).ToList()
        });
    Assert.IsFalse(foundMultiple.IsEmpty); что-то найти мы должны
    здесь собственно, применяем функциональный стиль для проверки равенства этих списков
    def found = foundMultiple.FoldLeft(foundMultiple.Head, (ring, ring') =>
    {
        mutable coincide = false;
        def warning = "Find Usages should produce the same results, disregarding on which usage a user places a cursor";
        try
        {
            coincide = FoldLeft2(ring, ring', true, (a, b, coincideToTheLeft) =>
                if (coincideToTheLeft) a.Location.CompareLines(b.Location) == 0 else false);
        }
        catch
        {
            | _ => coincide = false;
        }
        when (stopAfterFirstFailedTest)
            Assert.IsTrue(coincide, warning);
        ring
    });
    Write($"found $(found.Length) usages, checking for correspondance... ");
    
    а дальше нужно проверить, что найдено действительно то, что должно быть найденно, но это уже другая история...
    def success = FoundUsagesAreRight(testCase, shouldFindRing, found);
    def message = if (success) "ok" else "incorrect!.. saving changes...";
    WriteLine(message);
    success
}


вроде бы неплохой пример применения свёрток (по 1 списку и под 2 спискам) и лямбд
естественно, можно и циклами то же самое, но уже не нужно
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[6]: Требуются примеры использования first class function
От: PhantomIvan  
Дата: 22.11.06 15:25
Оценка:
а, ещё там затесался Map:
PI>
PI>    def shouldFindRing = MakeUsage(line, declaration, name, starter) ::
PI>        ScanSources(checkPhrase, testCase).Map((line, _, location, _) => MakeUsage(line, location, name, checkPhrase));
PI>


плюс эти функции для тестирования, аналогичные FindUsages объявляются с одной и той же сигнатурой, и потом "раннер" тестов проходит по их списку, вызывая одну за другой — вот функции как 1-класс ситизен
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[8]: Требуются примеры использования first class function
От: Кодт Россия  
Дата: 22.11.06 15:36
Оценка:
Здравствуйте, Programmierer AG, Вы писали:

>> inRegion {- x  p -} = ($) -- x $ p = p x
>> -- поэтому ниже мы его выплавим
PA>-- на самом деле inRegion = flip ($)


Э, позвольте!
flip ($) x y = ($) y x = y $ x = x y
flip ($) = id

Другое дело, что я очепятался в комментарии Вот она, блеск и нищета кратких идентификаторов.
Так будет понятнее:
point `inRegion` region = region point = point $ region
inRegion = ($)
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[9]: Требуются примеры использования first class function
От: Programmierer AG  
Дата: 22.11.06 15:43
Оценка:
Кодт wrote:
>
> point `inRegion` region = region point = point $ region
> inRegion = ($)
>

То ли у меня вырубились мозги (что неудивительно после соседнего ответа
Трурля на тему instance Monad((->)a)...), то ли ты упорно ошибаешься при
этом переходе:
region point = point $ region

($) не переставляет аргументы местами, f $ x = f x, проверь:
Prelude>:t ($)
($) :: (a -> b) -> a -> b
Posted via RSDN NNTP Server 2.0
Re[9]: Требуются примеры использования first class function
От: Programmierer AG  
Дата: 22.11.06 15:51
Оценка:
Кодт wrote:
>
> flip ($) = id
>

flip ($) не равен id, он эквивалентен (|>) из стандартной библиотеки F#,
я его использую каждый день для таких вот конвейеров:
key_value_pairs |>
sort (fun (_, x) (_, y) -> compare y x) |>
first 10 |> map fst |> String.concat ";" |> print_endline

Unix-way!
Posted via RSDN NNTP Server 2.0
Re[10]: Требуются примеры использования first class function
От: Кодт Россия  
Дата: 22.11.06 16:57
Оценка:
Здравствуйте, Programmierer AG, Вы писали:

PA>flip ($) не равен id, он эквивалентен (|>) из стандартной библиотеки F#,


Каюсь, заглючило.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[8]: JRuby, RubyCLR, IronPython - зачем?
От: Programmierer AG  
Дата: 22.11.06 17:23
Оценка:
Lazy Cjow Rhrr wrote:
> Ещё одно решение на Хаскеле. Я его спёр отсюдава:
> И опять же рекурсивный поиск с откатом: вон тама функция mark — это либо адванс, либо откат, в зависимости от того, как попадёт.
Отличная трава! Часа 3 курил . Реализация тормозная, но сколько
красивых фокусов! Замечательная иллюстрация ленивости — для меня как
новичка было совершенно неочевидно из кода, что все решения будут
выводиться на экран по мере нахождения.

С твоей интерпретацией функции mark я не согласен: это всегда один шаг в
пространстве решений, откатов тут нет. Тупиковые ветви дерева решений
отфильтруются потом:
    search p l = [mark (p,n) s | s <- l, n <- s p]
                                        -- ^^^^^^^^ здесь s p вернет
                                        -- пустой список, если позиция
                                        -- на доске бесперспективная


Кстати, еще один впечатляющий пример представления данных в виде функции
(это к вопросу: "Хм, интересная идея. А в чём преимущество по сравнению
с представлением области с помощью АТД?").
Posted via RSDN NNTP Server 2.0
Re[9]: Требуются примеры использования first class function
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.11.06 17:41
Оценка: :)))
Здравствуйте, ie, Вы писали:

ie>Аналогично! И вообще, час J с утра и рабочий день пропал


Хорошо вам. А я для этой цели по старинке водку да коньяк использую. А они денег стоят.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Требуются примеры использования first class function
От: PhantomIvan  
Дата: 22.11.06 18:10
Оценка:
ie>>Аналогично! И вообще, час J с утра и рабочий день пропал

VD>Хорошо вам. А я для этой цели по старинке водку да коньяк использую. А они денег стоят.


ты тоже с утра?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Требуются примеры использования first class function
От: FR  
Дата: 22.11.06 19:59
Оценка: 12 (1)
Здравствуйте, Gajdalager, Вы писали:

G>Вот то же, но со списками, паттерн матчингом и каррингом


Интересно только, код кажется стал менее понятным

Лучше примерно так:
def split(s, delim = lambda c : c in " \n\t\f\r\n\v", word = ""):
    if not s: return [word]
    
    if delim(s[0]): return [word] + split(s[1:], delim, "")
        
    return split(s[1:], delim, word + s[0])
Re[3]: Требуются примеры использования first class function
От: FR  
Дата: 22.11.06 20:01
Оценка:
Здравствуйте, Gajdalager, Вы писали:

G>Вот то же, но со списками, паттерн матчингом и каррингом


Еще тут Re: BOOST, .NET, String.Split и производительность…
Автор: VladD2
Дата: 21.09.06
тоже такое есть.
Re[2]: Требуются примеры использования first class function
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.11.06 20:22
Оценка: 17 (2)
Здравствуйте, FR, Вы писали:

Попытался создать гибридный аналог этих функций обладающий высоким быстродействием но в то же время более менее компактный и более понятный. Вот что из этого вышло:
Split2(str : string) : array[string]
{
    mutable i = 0; 
    def next () { if (i < str.Length) { def ch = str[i]; i++; ch } else '\0' } 
    def word = Text.StringBuilder();
    def words = Generic.List();
    def addWord() { when (word.Length != 0) { words.Add(word.ToString()); word.Length = 0; } }
    def split(_)
    {
        | '\t' | '\n' | '\'' | ' ' => addWord();          split(next())
        | '\0'                     => addWord();
        | x                        => _ = word.Append(x); split(next())
    }
    
    split(next());
    words.ToArray();
}

Практически никаких лишних действий или выделений памяти, но и результат не очень компактен. Хотя, по-моему, намного более понятный чем оба тваои варианта.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Требуются примеры использования first class function
От: FR  
Дата: 22.11.06 20:30
Оценка:
Здравствуйте, VladD2, Вы писали:

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


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


....

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


Интересно, но код уже не функциональный
Выделенное неправда
Re[4]: Требуются примеры использования first class function
От: FR  
Дата: 22.11.06 21:19
Оценка:
Здравствуйте, FR, Вы писали:

FR>Лучше примерно так:

FR>
FR>def split(s, delim = lambda c : c in " \n\t\f\r\n\v", word = ""):
FR>    if not s: return [word]
    
FR>    if delim(s[0]): return [word] + split(s[1:], delim, "")
        
FR>    return split(s[1:], delim, word + s[0])
FR>


еще вариант с ФВП, и без рекурсии:
def split2(s, delim = lambda c : c in " \n\t\f\r\n\v"):
    def _(sum, c):
        if delim(c): return sum + [""]
        return sum[:-1] + [sum[-1] + c]
        
    return reduce(_, s, [""])
Re[4]: Требуются примеры использования first class function
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.11.06 00:15
Оценка: +1
Здравствуйте, FR, Вы писали:

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


FR>Выделенное неправда


Это не правда или не правда. Это мое мнение. Ты конечно можешь с ним быт не согласен, но это уже твое мнение.

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

FR>Интересно, но код уже не функциональный


Я и говорю "гибридный". Но я в догматики ФП не записывался. Я выбираю решения на основе анализа разных факторов. "Просто" более короткий код не всегда лучше. А вот более короткий и эффективный другое дело.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Требуются примеры использования first class function и p
От: Зверёк Харьковский  
Дата: 23.11.06 02:52
Оценка: 1 (1)
Здравствуйте, VladD2, Вы писали:

VD>Когода кто-то пишет статьи о фунциональном программировании, то почему-то в качестве примеров всегда используются вещи вроде фунций Фибоначи и тому подобной бесполезной фигни.


VD>Это приводит к тому, что у людей закрадывается сомнение, что данные возможности полезны в области математики, парсинга или еще какой-то специализированной области оторванной от жизни.


VD>Предлагаю совместными усилиями подобрать набор примеров которые с одной стороны не требовали бы вникания в некоторую сложную задачу с другой демонстрировали приемущества функциональных языков (first class-функций, алгеброических типов, сопоставления с образцом).


VD>Приветсвуются любые примеры.


Ну, неплохой пример, в общем-то, на поверхности лежит:

widget.on_mouse_down {|button, x, y| ...} #функция-обработчик всех сообщений mouse_down
widget.on_mouse_down(LEFT_BUTTON) {|x, y| ...} #сюда паттерн-матчатся только left_mouse_down

#и т.п.
widget.on_key_press{|key, shifts| ...}
widget.on_key_press(Key::A){|shifts| ...}
widget.on_key_press(Key::A, Key::SHIFT){ ...}
widget.on_key_press(nil, Key::SHIFT){|key| ...}


Демонстрирует: передачу функции как параметра, ее хранение в переменной, паттерн-матчинг.
Ы?

По-моему, достаточно "близкий к телу" пример.
FAQ — це мiй ай-кью!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.