Здравствуйте, Lazy Cjow Rhrr, Вы писали:
M>>Всего лишь рекурсивный поиск с откатом, говоришь ? Трудно представить существенно разные решения говоришь ? M>>Красота!
LCR>Ну, прищучил... Но! Эта "красота" — рекурсивный поиск с откатом. Рекурсия хвостовая, и подбор-откат делается в параметрах.
Ну это да, идея больше относилась к существенно разным решениям. То есть идея то одна, а реализация в "Красоте" — ухх!
LCR>Тем не менее ты прав , не все решения упираются в рекурсивный поиск. Если подумать, можно ещё способы напридумывать.
Угу. Вывести какую-нибудь формулу для получения готового решения допустим, и записать ее в 1 строчку на J
... << RSDN@Home 1.2.0 Deep Purple — Maybe I'm A Leo >>
Re[6]: Требуются примеры использования first class function
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
К>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
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
плюс эти функции для тестирования, аналогичные FindUsages объявляются с одной и той же сигнатурой, и потом "раннер" тестов проходит по их списку, вызывая одну за другой — вот функции как 1-класс ситизен
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[8]: Требуются примеры использования first class function
> 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
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
ie>>Аналогично! И вообще, час J с утра и рабочий день пропал
VD>Хорошо вам. А я для этой цели по старинке водку да коньяк использую. А они денег стоят.
ты тоже с утра?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: Требуются примеры использования first class function
Здравствуйте, 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
Попытался создать гибридный аналог этих функций обладающий высоким быстродействием но в то же время более менее компактный и более понятный. Вот что из этого вышло:
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
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, FR, Вы писали:
VD>Попытался создать гибридный аналог этих функций обладающий высоким быстродействием но в то же время более менее компактный и более понятный. Вот что из этого вышло:
....
VD>Практически никаких лишних действий или выделений памяти, но и результат не очень компактен. Хотя, по-моему, намного более понятный чем оба тваои варианта.
Интересно, но код уже не функциональный
Выделенное неправда
Re[4]: Требуются примеры использования first class function
Здравствуйте, 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
Здравствуйте, FR, Вы писали:
VD>>Практически никаких лишних действий или выделений памяти, но и результат не очень компактен. Хотя, по-моему, намного более понятный чем оба тваои варианта.
FR>Выделенное неправда
Это не правда или не правда. Это мое мнение. Ты конечно можешь с ним быт не согласен, но это уже твое мнение.
Этот код мне кажется проще, так как в нем есть четка декомпозиция. Я легко читаю алгоримт. Вот мы выделяем слово, а вот добавляем его в список... В то же время чисто императивный вариант так велик, что за одтельными микро-действиями не видно сути алгоритма. А рекурсивный столь сжат, что его уже приходится расшивровывать. "Лишние" функции в этом примере я воспринимаю как документирование.
FR>Интересно, но код уже не функциональный
Я и говорю "гибридный". Но я в догматики ФП не записывался. Я выбираю решения на основе анализа разных факторов. "Просто" более короткий код не всегда лучше. А вот более короткий и эффективный другое дело.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Требуются примеры использования first class function и p
Здравствуйте, VladD2, Вы писали:
VD>Когода кто-то пишет статьи о фунциональном программировании, то почему-то в качестве примеров всегда используются вещи вроде фунций Фибоначи и тому подобной бесполезной фигни.
VD>Это приводит к тому, что у людей закрадывается сомнение, что данные возможности полезны в области математики, парсинга или еще какой-то специализированной области оторванной от жизни.
VD>Предлагаю совместными усилиями подобрать набор примеров которые с одной стороны не требовали бы вникания в некоторую сложную задачу с другой демонстрировали приемущества функциональных языков (first class-функций, алгеброических типов, сопоставления с образцом).
VD>Приветсвуются любые примеры.
Ну, неплохой пример, в общем-то, на поверхности лежит: