Delphi vs C++: функциональное программирование - ленивый список , решение конкретной задачи средствами заданных языков

[trainer]

Задача: Реализация ленивого списка [ленивых объектов]

Цель: сравнение удобства реализации абстракции "ленивый список" средствами указанных языков

Термины, определения и обозначения:

• Ленивый объект(обозначается elem) - объект, у которого создание отделено от вычисления его значения. Значение объекта вычисляется в момент, когда это значение понадобится, без явного вызова вычисления. При повторном обращении значение не вычисляется заново. Все побочные эффекты, связанные с вычислением объекта, должны проявляться не ранее чем в момент обращения.
• Ленивый список(обозначается list) - список ленивых объектов, которые создаются в момент обращения к ним.

Требования:
Ленивый список должен поддерживать следующие операции:

• 1) Создание пустого списка, обозначается list(). Размер такого списка равен 0;
• 2) Создание списка из одного элемента, обозначается list(elem). Размер такого списка равен 1;
• 3) Создание списка бесконечного размера, заданного начальным значением и приращением, обозначается list(elem, increment), каждый последующий элемент отличается от предыдущего на значение increment. Размер такого списка равен ???. Только для типов, поддерживающих приращение значения;
• 4) Создание списка, заданного начальным и конечным значениями и приращением, обозначается list(elem first_value, elem limit_value, increment). Размер такого списка равен количеству укладывающихся в заданный диапазон значений. Только для типов, поддерживающих приращение значения;
• 5) Оператор head, возвращающий первый элемент списка("голову"), обозначается head(list);
• 6) Оператор tail, возвращающий новый список, являющийся копией исходного без первого элемента("хвост"), обозначается tail(list);
• 7) Оператор map, применяющий заданную функции к каждому элементу списка, не изменяет длину списка, обозначается map(function, list);
• 8) Оператор cons, создающий новый список путем добавления к списку новой головы, обозначается cons(elem, list);
• 9) Оператор length, возвращающий длину списка, обозначается length(list);
• 10) Оператор filter, порождающий новый список, состоящий из копий элементов исходного списка, удовлетворяющих заданному в виде функции(функтора) критерию, обозначается filter(function, list);
• 11) Оператор take, порождающий новый список, состоящий из копий заданного числа элементов исходного списка начиная с головы, обозначается take(number, list);

Все операторы не вызывают вычисления еще не вычисленных значений элементов списка. К порождаемым спискам предъявляются все требования, предъявляемые к ленивым спискам.

Тестовое задание:
<тут должно быть тестовое задание>

Сообщение отредактировано: trainer - 23.09.10, 09:46

[korvin]

Цитата Romkin @ 21.09.10, 12:40

Цитата trainer @ 21.09.10, 11:59

4) Создание списка, заданного начальным и конечным значениями и приращением, обозначается list(elem first_value, elem limit_value, increment). Размер такого списка равен количеству укладывающихся в заданный диапазон значений;

Вот этот пункт явно указывает, что список у нас из чисел. А если объекты?
Мне хотелось бы разделить реализации списков чисел и списков объектов, в Delphi проблемы с арифметикой на дженериках

смотря какие объекты. в хацкелле таким образом можно использовать любые типы, для которых определён экземпляр класса Enum (по-вашему любые типы, реализующие интерфейс Enum, я так понимаю в С++ это итераторы всякие)

Prelude> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz" -- в хаскелле строки -- это списки [Char]
Prelude> :info Char
data Char = GHC.Types.C# GHC.Prim.Char#     -- Defined in GHC.Types
...
instance Enum Char -- Defined in GHC.Enum
...
Prelude> :info Enum
class Enum a where
  succ :: a -> a
  pred :: a -> a
  toEnum :: Int -> a
  fromEnum :: a -> Int
  enumFrom :: a -> [a]
  enumFromThen :: a -> a -> [a]
  enumFromTo :: a -> a -> [a]
  enumFromThenTo :: a -> a -> a -> [a]
    -- Defined in GHC.Enum
instance Enum Ordering -- Defined in GHC.Enum
instance Enum Int -- Defined in GHC.Enum
instance Enum Char -- Defined in GHC.Enum
instance Enum Bool -- Defined in GHC.Enum
instance Enum () -- Defined in GHC.Enum
instance Enum Integer -- Defined in GHC.Num
instance Enum Float -- Defined in GHC.Float
instance Enum Double -- Defined in GHC.Float
Prelude>

Добавлено 21.09.10, 12:51

Цитата IL_Agent @ 21.09.10, 12:40

А я бы и на коробочные решения посмотрел. Для общего развития, так сказать

ну посмотри на хаскелл =)

[IL_Agent]

Цитата korvin @ 21.09.10, 12:49

ну посмотри на хаскелл =)

Уже смотрел. Планирую смотреть ещё.

[trainer]

Цитата IL_Agent @ 21.09.10, 12:49

Видимо, с оглядкой на Хаскелевские [1,3 ..]

Не столько с оглядкой, сколько для удобства описания числовых последовательностей.

Добавлено 21.09.10, 12:55

Цитата IL_Agent @ 21.09.10, 12:49

и функцией приращения

Для того же C++ это в общем-то лишнее ограничение.

[IL_Agent]

Цитата trainer @ 21.09.10, 12:52

Для того же C++ это в общем-то лишнее ограничение.

Разве это ограничение ? Наоборот: требовать определения операторов для элементов - это ограничение, по-моему...

Добавлено 21.09.10, 13:01
Хотя, я думаю, это не принципиально. Можно оставить требования как есть. А в Делфи для числовых реализаций дженериков можно хелперов (или чего там есть аналогичное методам-расширениям из шарпа) наплодить, например

Сообщение отредактировано: IL_Agent - 21.09.10, 13:03

[Romkin]

Цитата IL_Agent @ 21.09.10, 12:58

А в Делфи для числовых реализаций дженериков можно хелперов (или чего там есть аналогичное методам-расширениям из шарпа) наплодить, например

Да нет. Скажем так, выставить требование, чтобы у объекта интерфейс был определенный могу, но тут сразу отлетают примитивные типы. Могу объявить, что требуется отдельный преобразователь для приращения, вот это уже более подходяще. Только иерархию классов определить.

[IL_Agent]

Цитата Romkin @ 21.09.10, 13:05

Да нет. Скажем так, выставить требование, чтобы у объекта интерфейс был определенный могу, но тут сразу отлетают примитивные типы. Могу объявить, что требуется отдельный преобразователь для приращения, вот это уже более подходяще. Только иерархию классов определить.

Я вот чего имел в виду. Пример на шарпе:

class LazyList<T>
{
   public LazyList(T start_value, Func<T,T> inc){...};
   public LazyList<T> Cons(LazyList<T> other){...};
...
}
 
static class LazyListExtensions
{
  public static LazyList<int> ConsIntSeq(this LazyList<int> list, int start_value, int increment)
  {
    return list.Cons(new LazyList<int>(start_value, n=>n+increment));
  }
}

И теперь можно получить список чисел так:

var lst = new LazyList<int>().Cons(1,3);

Сообщение отредактировано: IL_Agent - 21.09.10, 13:19

[trainer]

Цитата IL_Agent @ 21.09.10, 12:58

Наоборот: требовать определения операторов для элементов - это ограничение, по-моему...

Почему требовать? Хочешь - определяешь, не хочешь - такой вариант создания не применяется. Я могу разбить на подпункты - тогда появляется фишка с неконстантным/нелинейным приращением. Как мне сформулировать определение длины последовательности в этом случае? Сможете с таким поведением реализовать остальной функционал?

Сообщение отредактировано: trainer - 21.09.10, 13:57

[Romkin]

Консультация требуется. Является ли данная конструкция ленивым списком?

type
  TElement<T> = reference to function: T;
 
  TConverter<T> =
    reference to function(Elem: TElement<T>; Index: integer): TElement<T>;
 
 
  ILazyList<T> = interface
    function GetHead: T;
    function GetTail: ILazyList<T>;
 
    property Head: T read GetHead;
    property Tail: ILazyList<T> read GetTail;
  end;
 
  TLazyList<T> = class(TInterfacedObject, ILazyList<T>)
  private
    FValue: T;
    FStored: boolean;
    FElement: TElement<T>;
    FConverter: TConverter<T>;
    FIndex: integer;
  protected
    function GetHead: T;
    function GetTail: ILazyList<T>;
  public
    constructor Create(FirstElem: TElement<T>; Converter: TConverter<T>); virtual;
  end;
 
implementation
 
{ TLazyList<T> }
 
constructor TLazyList<T>.Create(FirstElem: TElement<T>;
  Converter: TConverter<T>);
begin
  FElement := FirstElem;
  FConverter := Converter;
end;
 
function TLazyList<T>.GetHead: T;
begin
  if FStored then
    Result := FValue
  else
  begin
    Result := FElement; //вычисляем
    FValue := Result;
    FStored := True;
  end;
end;
 
function TLazyList<T>.GetTail: ILazyList<T>;
var
  ALazyList: TLazyList<T>;
begin
  ALazyList := TLazyList<T>.Create(FConverter(FElement, FIndex + 1),
    FConverter);
  ALazyList.FIndex := FIndex + 1;
  Result := ALazyList;
end;

Вот ее применение:

var
  intLazyList, L1, L2: ILazyList<integer>;
  i: integer;
 
begin
  try
    intLazyList := TLazyList<integer>.Create(
      function: integer begin Exit(0) end,
      function(Elem: TElement<integer>; Index: integer): TElement<integer>
        begin
          Result := function: integer
            begin
              Result := Index;
              writeln('Calc N ', Index);
            end;
        end);
    for i := 0 to 9 do
    begin
      writeln(intLazyList.Head);
      intLazyList := intLazyList.Tail;
    end;
    writeln;
    L1 := intLazyList.Tail.Tail.Tail;
    L2 := intLazyList.Tail;
    writeln('Calc!');
    writeln(L1.Head);
    writeln(L2.Head);
    readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;

Вывод:

Цитата

0
Calc N 1
1
Calc N 2
2
Calc N 3
3
Calc N 4
4
Calc N 5
5
Calc N 6
6
Calc N 7
7
Calc N 8
8
Calc N 9
9

Calc!
Calc N 13
13
Calc N 11
11

Я говорю о строках после Calc!

То есть, реализовал пока только head и tail, идти дальше?
А то я уже запутался

[korvin]

Цитата Romkin @ 21.09.10, 14:20

Вот ее применение:

...
      function(Elem: TElement<integer>; Index: integer): TElement<integer>
        begin
          Result := function: integer
            begin
              Result := Index;
              writeln('Calc N ', Index);
            end;
        end);
...

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

и что было выше

function :integer; begin Exit(0) end

?

Сообщение отредактировано: korvin - 21.09.10, 17:35

[IL_Agent]

Romkin, можешь камменты добавить ? Или словами объяснить ? А то ну уж очень тяжело эти бегин-енды читаются, для не привыкшего глаза

Добавлено 21.09.10, 18:31

Цитата trainer @ 21.09.10, 13:54

Я могу разбить на подпункты - тогда появляется фишка с неконстантным/нелинейным приращением. Как мне сформулировать определение длины последовательности в этом случае? Сможете с таким поведением реализовать остальной функционал?

Меня устраивают существующие требования.

[Romkin]

Цитата IL_Agent @ 21.09.10, 18:31

Romkin, можешь камменты добавить ? Или словами объяснить ? А то ну уж очень тяжело эти бегин-енды читаются, для не привыкшего глаза

Для привыкшего - тоже. Првда, постепенно привыкаю.

Цитата korvin @ 21.09.10, 17:34

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

Это уберется позже, будут готовые "заготовки", классы, обеспечивающие разные стандартные варианты списка. Но и такой способ инициализации думаю оставить.
Основная идея в том, что список инициализируется не значениями (данными), а методами, способами получения стартового элемента и перехода от предыдущего элемента к следующему. Для бесконечного списка, как более простой реализации нежели конечный, достаточно этих двух описаний.
Таким образом, TElement<T> - это метод, который вернет элемент списка типа T при своем вызове. Соотвественно, TConverter<T> - метод, который принимает предыдущий элемент и выдает следующий. Поскольку элементы при этом не вычисляются, то в качестве "элементов" и выступают абстрактные функции TElement.
Для простейшего варианта списка, который считает от начала и следующий элемент получается из предыдущего, этого достаточно.
TLazyList - собственно список, интерфейс - для моего удобства, контроль времени жизни идет путем подсчета ссылок.
Ситуация простая: у элемента списка есть метод, который выдает значение при вызове, он запоминается в FElement, вычисляется при обращении к Head (см GetHead). Получение остатка производится через Tail, выдается "хвост", такой же список, но FElement которого содержит метод, вычисляющий следующий по счету элемент. Переход осуществляется через конвертер, который конструирует метод для следующего элемента.
В данном примере организуется список натуральных чисел, если посмотреть на сигнатуру конструктора, то инициализация

intLazyList := TLazyList<integer>.Create(
      function: integer begin Exit(0) end,
      function(Elem: TElement<integer>; Index: integer): TElement<integer>
        begin
          Result := function: integer
            begin
              Result := Index;
              writeln('Calc N ', Index);
            end;
        end);

подразумевает, что стартовый элемент списка, FirstElem - это функция

function: integer;
begin
  Exit(0)
end;

, возвращающая 0.
А переход к следующему элементу задается так:

function(Elem: TElement<integer>; Index: integer): TElement<integer>
        begin
          Result := function: integer
            begin
              Result := Index;
              writeln('Calc N ', Index);
            end;
        end

, просто порядковый номер (Result := Index;) плюс побочный эффект при переходе к следующему элементу для демонстрации.
Хотя более правильным было написать Result := Elem + 1; - следующий элемент это предыдущий плюс один.
В ветке Delphi vs C++ я демонстрировал список факториалов, где первый элемент - метод, возвращающий 1, а следующий - Elem*Index. (Index считается строго от 0).
Непосредственный вызов метода Elem в выражении Result := Elem + 1; или подобном - кажущийся. Результат работы конвертера - функция, код которой выполнится только при ее вызове (см GetHead, Result := FElement). Если используется предыдущая функция, Elem, вызов пойдет рекурсивно по созданной цепочке.
Ну а комментарии - завтра...

[korvin]

Цитата Romkin @ 21.09.10, 19:51

Основная идея в том, что список инициализируется не значениями (данными), а методами, способами получения стартового элемента и перехода от предыдущего элемента к следующему.

это понятно, просто это должно быть скрыто в реализации, пользователь не должен мочь запихнуть неленивые объекты/значения.

Добавлено 21.09.10, 19:56

Цитата Romkin @ 21.09.10, 19:51

подразумевает, что стартовый элемент списка, FirstElem - это функция

function: integer;
begin
  Exit(0)
end;

, возвращающая 0.
А переход к следующему элементу задается так.

это всё должно быть скрыто в реализации абстракции

[trainer]

Цитата korvin @ 21.09.10, 12:24

я даже не буду предоставлять реализацию на CL, если не попросят

Я тебе предложу подготовить тестовое задание для проверки реализаций. Можешь сделать?

[korvin]

Цитата trainer @ 22.09.10, 04:45

Я тебе предложу подготовить тестовое задание для проверки реализаций. Можешь сделать?

вечером только (примерно после 19:00 по МСК), сегодня весь день занят буду

[Romkin]

Цитата korvin @ 21.09.10, 19:54

это всё должно быть скрыто в реализации абстракции

Ну не совсем скрыто будет, я планирую оставить возможность делать произвольные списки.
Тут вопрос возник, по поводу cons. Сделал, я, допустим список от 1 с шагом 2, и присоединил голову 10. И что теперь должно получиться?