Здравствуйте, achp, Вы писали:
A>Здравствуйте, Аноним, Вы писали:
А>>Тут целая квантовая теория выходит Чтобы прочитать енумератор, надо изменить его состояние. От этого печального факта никуда не денешся.
A>Я тут делал маленькие развлечения на Эф-шарпе и ничего лучше не смог придумать как складывать уже прочитанную часть перечисления в списке. При этом есть ещё такая проблема как возможность гонок. В итоге в общем виде сопоставление перечислений оказывается не очень эффективной вещью.
В принципе можно сделать немного иначе. Ввести в язык новый тип списков — lazy_list. Один из конструкторов такого списка может принимать на вход IEnumerable. Сопоставление производить аналогично list.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Помнится, как-то затрагивалась тема касательно того, что неплохо было бы добавить специальный образец для Enumerable. Вот, собственно, интересно — как бы мог выглядеть этот образец (предполагается, что будет возможен "рекурсивный" разбор на манер списка с образцом голова-хвост x::xs). Т.е. синтаксис, поведение?
В OCaml есть паттерн матчинг потоков (streams) описание тут:
Кратко сопоставление уничтожающее, то есть если образец совпадает то он убирается из потока, кроме того
можно рекурсивно вызывать для остатка потока функцию разбора, вот небольшой пример фильтрует символьный
поток оставляя в нем только цифры:
let digit c = c>='0' && c<='9'
let rec tst = parser
| [< 'c when digit c; r=tst >] -> (String.make 1 c) ^ r
| [<'x; r=tst>] -> r;
| [<>] -> ""
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, Воронков Василий, Вы писали:
ВВ>>Термин generator достаточно распространен. Погугли на, скажем, generators in Scheme — наверняка найдешь несколько примеров реализации этого дела на макросах.
FDS>Что-то не гуглится. Есть только генераторы кода, генераторы цветовых схем, кварцевые генераторы и т.д.
Здравствуйте, FDSC, Вы писали:
FDS>Стоп-стоп-стоп. Разве генератор в ФЯ не принимает как раз положение в списке? FDS>Т.е., грубо говоря, если у меня есть бесконечный список, он ведь не запоминает в себе, на каком месте он остановился, он ведь принимает или номер, или элемент списка, разве нет?
Генератор — это генератор. Списки тут не причем. Причем тут вообще номер или элемент списка? Вы вообще представляете как итераторы в дотнете работают? А дотнетовские итераторы — это классический пример генераторов. С помощью генераторов (ну шире — корутин) можно, к примеру, реализовать кооперативную многопоточность.
Генератор — это функция, которую можно вызывать несколько раз, и она продолжается с того момента, на котором выполнение было прервано. Не просто продолжается с того же момента, но восстанавливает все свое состояние (значение локальных переменных) и пр.
Помнится, как-то затрагивалась тема касательно того, что неплохо было бы добавить специальный образец для Enumerable. Вот, собственно, интересно — как бы мог выглядеть этот образец (предполагается, что будет возможен "рекурсивный" разбор на манер списка с образцом голова-хвост x::xs). Т.е. синтаксис, поведение?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Помнится, как-то затрагивалась тема касательно того, что неплохо было бы добавить специальный образец для Enumerable. Вот, собственно, интересно — как бы мог выглядеть этот образец (предполагается, что будет возможен "рекурсивный" разбор на манер списка с образцом голова-хвост x::xs). Т.е. синтаксис, поведение?
Самый примитивный способ, до которого я додумался, это Seq(head, tail) и Seq() (ну, или IEnumerable(head, tail) и IEnumerable).
Поведение: при первом (только при первом!) Seq-матче вызывается метод MoveNext(), и если возвращается true, Current матчится с head а tail — с самим объектом Enumerable. Если возвращается false, запускается ветка с Seq(). Достоинства: не вводится новая пунктуация (вообще не вводится новый синтаксис, можно сказать), образцы аналогичны с образцами рекордов. Недостатки: выглядит не так круто, как матчинг по спискам.
Re[2]: IEnumerable и паттерн матчинг
От:
Аноним
Дата:
20.05.10 15:08
Оценка:
Здравствуйте, catbert, Вы писали:
C>Самый примитивный способ, до которого я додумался, это Seq(head, tail) и Seq() (ну, или IEnumerable(head, tail) и IEnumerable).
Но в душе хочется F-шарповских Active Patterns, только покруче.
Здравствуйте, catbert, Вы писали:
C>Самый примитивный способ, до которого я додумался, это Seq(head, tail) и Seq() (ну, или IEnumerable(head, tail) и IEnumerable). C>Поведение: при первом (только при первом!) Seq-матче вызывается метод MoveNext(), и если возвращается true, Current матчится с head а tail — с самим объектом Enumerable. Если возвращается false, запускается ветка с Seq(). C>Достоинства: не вводится новая пунктуация (вообще не вводится новый синтаксис, можно сказать), образцы аналогичны с образцами рекордов. C>Недостатки: выглядит не так круто, как матчинг по спискам.
Тут проблема какая... В принципе можно и вообще без tail обойтись, собственно, мы же с одним и тем же объектом работаем. Но это-то и таит в себе опасности. Скажем если у нас справа будет что-нибудь типа func1(seq) && func2(seq), то в func2 энумератор уже будет передан с совершенно другим состоянием, чем в func1. Т.е. прямолинейная реализация типа seq(x, y, z) как-то невольно располагает к побочным эффектам.
Здравствуйте, catbert, Вы писали:
C>Недостатки: выглядит не так круто, как матчинг по спискам.
Ещё одним недостатком является немудрое поведение в таком матче:
match (xs)
{
| Seq(x, Seq(y, Seq()) ) => // blah blah
| Seq(x, Seq(y, Seq(z, Seq()) ) ) => // а тут проблема, ведь на предыдущей ветке вызвали MoveNext три раза, соответственно Current "уже не тот"
}
Исправляется такое, например, кешированием первых елементов xs.
Вообще, паттерн-матчинг по изменяемым структурам, как я уже говорил — гадкая вещь
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Воронков Василий, Вы писали: ВВ>>Как тут быть? А>Тут целая квантовая теория выходит Чтобы прочитать енумератор, надо изменить его состояние. От этого печального факта никуда не денешся.
Самый тупой способ делать Reset на каждом вхождении match-а. Но если подумать, то даже с Reset-ом проблема, ибо мы энумератор к нам мог прийти уже с каким-то состоянием, отличном от нулевого. Причем это будет типичная ситуация — при рекурсивном разборе sequence-а.
Т.е. нужен какой-то умный reset? Или хитрое клонирование энумераторов?
Здравствуйте, catbert, Вы писали:
C>Исправляется такое, например, кешированием первых елементов xs. C>Вообще, паттерн-матчинг по изменяемым структурам, как я уже говорил — гадкая вещь
Тут проблема не в изменяемости структуры, а в том, что эта структура инкапсулирует некоторое состояние, которое приходится менять во время матча.
А с массивами таких проблем нет, ты, конечно, можешь там сам что-нибудь накосячить, ну так и варианты могут быть вполне себе изменяемыми структурами.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Самый тупой способ делать Reset на каждом вхождении match-а. Но если подумать, то даже с Reset-ом проблема, ибо мы энумератор к нам мог прийти уже с каким-то состоянием, отличном от нулевого. Причем это будет типичная ситуация — при рекурсивном разборе sequence-а. ВВ>Т.е. нужен какой-то умный reset? Или хитрое клонирование энумераторов?
PeekValue(enu : Seq[T]) : option[T * Seq[T]]
{
if (enu.MoveNext()) Some(enu.Current, Append(enu.Current, enu)) else None();
}
Append(elem : T, enu : Seq[T]) : Seq[T]
{
yield elem;
foreach (elem in enu) yield enu; // так делать ужасно, но это можно переписать без генератора
}
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Самый тупой способ делать Reset на каждом вхождении match-а. Но если подумать, то даже с Reset-ом проблема, ибо мы энумератор к нам мог прийти уже с каким-то состоянием, отличном от нулевого.
Мне кажется, матчить следует только IEnumerable. Не зря в Микрософте разделили эти интерфейсы.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, catbert, Вы писали:
C>>Кстати, можно брать новые IEnumerator'ы для каждого матча.
ВВ>Ну вот это пока единственный рабочий вариант. Но для этого придется их как-то клонировать.
Зачем клонировать? Мы матчим IEnumerable. Для каждого матча можно вызвать GetEnumerator().
Здравствуйте, Ziaw, Вы писали:
ВВ>>Здравствуйте, catbert, Вы писали: C>>>Кстати, можно брать новые IEnumerator'ы для каждого матча. ВВ>>Ну вот это пока единственный рабочий вариант. Но для этого придется их как-то клонировать. Z>Зачем клонировать? Мы матчим IEnumerable. Для каждого матча можно вызвать GetEnumerator().
А чем это отличается от полного Reset? Состояние-то надо сохранять.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Помнится, как-то затрагивалась тема касательно того, что неплохо было бы добавить специальный образец для Enumerable. Вот, собственно, интересно — как бы мог выглядеть этот образец (предполагается, что будет возможен "рекурсивный" разбор на манер списка с образцом голова-хвост x::xs). Т.е. синтаксис, поведение?
Спор ни о чём: пытаетесь нефункциональщину запихнуть в функциональный язык. Тогда уж надо просто скопировать инумератор в список, а потом уже с ним базар устраивать...
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, Воронков Василий, Вы писали:
ВВ>>Помнится, как-то затрагивалась тема касательно того, что неплохо было бы добавить специальный образец для Enumerable. Вот, собственно, интересно — как бы мог выглядеть этот образец (предполагается, что будет возможен "рекурсивный" разбор на манер списка с образцом голова-хвост x::xs). Т.е. синтаксис, поведение?
FDS>Спор ни о чём: пытаетесь нефункциональщину запихнуть в функциональный язык. Тогда уж надо просто скопировать инумератор в список, а потом уже с ним базар устраивать...
1. Спора нет
2. Идею о паттерн-матчинге для энумераторов выдвигал вообще-то Влад
3. Немерле — не функциональный язык, а гибридный
4. Каким бы странным вам это не показалось, но генераторы (реализацией которых являются итераторы в дотнете) пришли именно из ФЯ
Здравствуйте, catbert, Вы писали:
ВВ>>Самый тупой способ делать Reset на каждом вхождении match-а. Но если подумать, то даже с Reset-ом проблема, ибо мы энумератор к нам мог прийти уже с каким-то состоянием, отличном от нулевого. C>Мне кажется, матчить следует только IEnumerable. Не зря в Микрософте разделили эти интерфейсы.
Разделили не зря, но как можно матчить только IEnumerable, я не очень понимаю. Состояние-то все же надо сохранять для рекурсивного разбора. А состояние хранит именно энумератор.
Здравствуйте, FDSC, Вы писали:
ВВ>>4. Каким бы странным вам это не показалось, но генераторы (реализацией которых являются итераторы в дотнете) пришли именно из ФЯ FDS>Если я не ошибаюсь, то там это просто рекурсивный поиск по списку без сохранения состояния, или я что-то не понимаю?
Это вы о чем-то совсем другом.
С помощью генератора можно представить, к примеру, бесконечный список. Т.е. в прямом смысле бесконечный. Генератор — частный случай корутины и неважно как она реализована в конкретном языке, все равно состояние должно быть по определению — т.е. при вызове функции исполнение должно продолжаться с того же момента, на котором оно прервалось.
Итераторы в дотнете — суть классические генераторы.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, FDSC, Вы писали:
ВВ>>>4. Каким бы странным вам это не показалось, но генераторы (реализацией которых являются итераторы в дотнете) пришли именно из ФЯ FDS>>Если я не ошибаюсь, то там это просто рекурсивный поиск по списку без сохранения состояния, или я что-то не понимаю?
ВВ>Это вы о чем-то совсем другом. ВВ>С помощью генератора можно представить, к примеру, бесконечный список. Т.е. в прямом смысле бесконечный. Генератор — частный случай корутины и неважно как она реализована в конкретном языке, все равно состояние должно быть по определению — т.е. при вызове функции исполнение должно продолжаться с того же момента, на котором оно прервалось. ВВ>Итераторы в дотнете — суть классические генераторы.
Стоп-стоп-стоп. Разве генератор в ФЯ не принимает как раз положение в списке?
Т.е., грубо говоря, если у меня есть бесконечный список, он ведь не запоминает в себе, на каком месте он остановился, он ведь принимает или номер, или элемент списка, разве нет?
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Генератор — это функция, которую можно вызывать несколько раз, и она продолжается с того момента, на котором выполнение было прервано. Не просто продолжается с того же момента, но восстанавливает все свое состояние (значение локальных переменных) и пр.
Стоп. Я думал, что вот это генератор
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
Нет?
Если нет, тогда каким образом вообще генератор может быть реализован в ФЯ?
В SICP такого слова как "генератор" вообще, вроде бы, нет.
Здравствуйте, FDSC, Вы писали:
FDS>Стоп. Я думал, что вот это генератор FDS>
FDS>(define (fibgen a b)
FDS>(cons-stream a (fibgen b (+ a b))))
FDS>(define fibs (fibgen 0 1))
FDS>
FDS>Нет?
Это не генератор.
FDS>Если нет, тогда каким образом вообще генератор может быть реализован в ФЯ? FDS>В SICP такого слова как "генератор" вообще, вроде бы, нет.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, FDSC, Вы писали:
FDS>>Стоп. Я думал, что вот это генератор FDS>>
FDS>>(define (fibgen a b)
FDS>>(cons-stream a (fibgen b (+ a b))))
FDS>>(define fibs (fibgen 0 1))
FDS>>
FDS>>Нет?
ВВ>Это не генератор.
FDS>>Если нет, тогда каким образом вообще генератор может быть реализован в ФЯ? FDS>>В SICP такого слова как "генератор" вообще, вроде бы, нет.
ВВ>Например, через замыкания.
Что именно через замыкания? Вверху тоже замыкание есть.
Здравствуйте, Аноним, Вы писали:
C>>Самый примитивный способ, до которого я додумался, это Seq(head, tail) и Seq() (ну, или IEnumerable(head, tail) и IEnumerable). А>Но в душе хочется F-шарповских Active Patterns, только покруче.
Здравствуйте, FDSC, Вы писали:
FDS>Что именно через замыкания?
Термин generator достаточно распространен. Погугли на, скажем, generators in Scheme — наверняка найдешь несколько примеров реализации этого дела на макросах.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Термин generator достаточно распространен. Погугли на, скажем, generators in Scheme — наверняка найдешь несколько примеров реализации этого дела на макросах.
Что-то не гуглится. Есть только генераторы кода, генераторы цветовых схем, кварцевые генераторы и т.д.
Здравствуйте, Аноним, Вы писали:
А>Тут целая квантовая теория выходит Чтобы прочитать енумератор, надо изменить его состояние. От этого печального факта никуда не денешся.
Я тут делал маленькие развлечения на Эф-шарпе и ничего лучше не смог придумать как складывать уже прочитанную часть перечисления в списке. При этом есть ещё такая проблема как возможность гонок. В итоге в общем виде сопоставление перечислений оказывается не очень эффективной вещью.
Здравствуйте, hardcase, Вы писали:
H>В принципе можно сделать немного иначе. Ввести в язык новый тип списков — lazy_list. Один из конструкторов такого списка может принимать на вход IEnumerable. Сопоставление производить аналогично list.
Так я что-то подобное и делал. Единственное, в чём разница, — в Эф-шарпе тип 'a seq соответствует уже IEnumerator. С точки зрения проблем реализации, шаг, отделяющий IEnumerable от IEnumerator, несуществен.
Здравствуйте, FDSC, Вы писали:
FDS>Спор ни о чём: пытаетесь нефункциональщину запихнуть в функциональный язык.
Для строгих (энергичных) функциональных языков это норма жизни
То есть некий объект сохраняющий и изменяющий свое состояние и вокруг него
функциональная обвязка, как пример те же потоки и ленивые списки в OCaml,
или наиболее ярко енумераторы в окамловских батарейках (батарейки это библиотека
претендующая на замену стандартной, аналог буста из C++) http://thelema.github.com/AAA-batteries/hdoc/BatEnum.html
Здравствуйте, Ziaw, Вы писали:
Z>Зачем клонировать? Мы матчим IEnumerable. Для каждого матча можно вызвать GetEnumerator().
А если под IEnumerable скрывается запрос в БД? Получится по одному запросу на матч.
Нужно обязательно мемоизовывать исходную последовательность. Это решит проблему и с повторяемостью, и позволит перечислять источник только один раз.
При этом заматченный хвост tail и сам матч m целиком
| seq(1, 2, tail) as m
будут возвращаться уже из мемоизованного источника.
Здравствуйте, i1yich, Вы писали:
Z>>Зачем клонировать? Мы матчим IEnumerable. Для каждого матча можно вызвать GetEnumerator().
I>А если под IEnumerable скрывается запрос в БД? Получится по одному запросу на матч.
I>Нужно обязательно мемоизовывать исходную последовательность. Это решит проблему и с повторяемостью, и позволит перечислять источник только один раз. I>При этом заматченный хвост tail и сам матч m целиком
| seq(1, 2, tail) as m
будут возвращаться уже из мемоизованного источника.
Я думал над этим. Мемоизовывать можно, только лениво, на каждом матче. Только c синтаксисом непонятно, как здесь различить любой остаток и последний элемент?
Здравствуйте, Ziaw, Вы писали:
Z>Только c синтаксисом непонятно, как здесь различить любой остаток и последний элемент?
Это несложно:
| seq(1, 2 .. tail) as m => ...
или в стиле Пролога
| seq(1, 2 | tail) as m => ...
или всегда считать последний элемент хвостом:
| seq(1, 2, last, ()) as m => ... // хвост пуст
| seq(1, 2, tail) as m => ... // хвост — tail
Мне непонятно, зачем "as m".
Ну, и мемоизация означает отжирание памяти, невидимое нетренированному глазу. В большинстве случаев это будет означать дублирование существующей коллекции. А в случае использования такой конструкции с бесконечными IEnumerable возможна даже утечка памяти.
Здравствуйте, achp, Вы писали:
A>Так я что-то подобное и делал. Единственное, в чём разница, — в Эф-шарпе тип 'a seq соответствует уже IEnumerator. С точки зрения проблем реализации, шаг, отделяющий IEnumerable от IEnumerator, несуществен.
Это уже есть. LazyList из FSharpPowerPack. Фактически, это поток. Превращается seq в поток достаточно просто:
module LazyList =
/// Build a new collection from the given enumerable object
val ofSeq: seq<'T> -> LazyList<'T>
Для потока определен активный паттерн-матчинг:
val (|Cons|Nil|) : LazyList<'T> -> Choice<('T * LazyList<'T>),unit>
Поток так устроен, что там уже ничего не перевычисляется.
Чтобы прочитать енумератор, надо изменить его состояние. От этого печального факта никуда не денешся.
