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

[trainer]

У меня конец рабочего дня, уже туго соображаю. Принимаются пожелания, замечания и уточнения. После полировки ТЗ его обсуждение будет вынесено в отдельную тему, чтобы не мешалось.
Вопросы:
1) Нужно ли создание списка, заданного перечислением значений вида list(1,3,5,7,9,13,19)? Соответственно, появится возможность писать list(1, list(3, 5, 7, 9))
2) какой примем длину бесконечного списка?

Добавлено 21.09.10, 12:02
Можно ввести веса для каждого пункта и оценивать полноту реализации. Можно для пунктов требования ввести вариант-минимум и вариант-максимум с соответствующими оценками.

[IL_Agent]

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

1) Нужно ли создание списка, заданного перечислением значений вида list(1,3,5,7,9,13,19)? Соответственно, появится возможность писать list(1, list(3, 5, 7, 9))

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

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

2) какой примем длину бесконечного списка?

Длина ленивого списка - ленивый объект, вычисляемый в момент обращения. Для бесконечного списка его вычисление уходит в бесконечный цикл ???

Добавлено 21.09.10, 12:16
И раз вынесли в отдельную тему, может не стоит ограничиваться двумя языками ?

[trainer]

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

Для бесконечного списка его вычисление уходит в бесконечный цикл ???

Ну мы можем для себя принять какое-то определенное значение. Скажем -1. Или максимально большое целое. Или индекс последнего(самого дальнего от головы) вычисленного элемента. Или еще что-то.

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

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

Ну если есть такое желание - почему бы и нет. Только чтобы решение было на этом языке и не "из коробки".

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

[korvin]

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

Длина ленивого списка - ленивый объект, вычисляемый в момент обращения. Для бесконечного списка его вычисление уходит в бесконечный цикл?

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

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

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

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

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

[Romkin]

trainer, ну вот ты пишешь задание чисто "под С++". В Delphi некоторые вещи просто излишни. Ладно, напишу я функцию list, а зачем? Почему конструктором список не создавать?

Добавлено 21.09.10, 12:33
Или почему я не могу иметь иерархию объектов-списков типа конечный-бесконечный?

[IL_Agent]

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

Ну мы можем для себя принять какое-то определенное значение. Скажем -1. Или максимально большое целое. Или индекс последнего(самого дальнего от головы) вычисленного элемента. Или еще что-то.

Проблем в том, как мы узнаем, что список бесконечен ? Например, исходя из предложенных тобой требований, построение списка чисел Фибоначчи мне видится таким (на псевдокоде):

fibs = list(0,1)
fibs = zip(plus, fibs, tail(fibs)) или fibs = fibs.zip(plus, fibs.tail)

И как тут узнать, что у него бесконечная длина ?

[korvin]

да, кстати, пустой список можно сделать константой (ну если это не будет сложнее в выбранном языке, чем конструктор)

[IL_Agent]

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

Ладно, напишу я функцию list, а зачем? Почему конструктором список не создавать?

Это не принципиально. Главное функционал, а не синтаксис.

[trainer]

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

Ладно, напишу я функцию list, а зачем? Почему конструктором список не создавать?

Все обозначения в ТЗ введены для удобства написания ТЗ и в частности для написания тестового задания. Детали реализации - твое дело. Мне кажется, что в C++ создаваться списки будут посредством соответствующих конструкторов.

[Romkin]

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

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

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

[IL_Agent]

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

Только чтобы решение было на этом языке и не "из коробки".

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

[Romkin]

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

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

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

[trainer]

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

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

Ну если только вне конкурса.

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

Вот этот пункт явно указывает, что список у нас из чисел. А если объекты?

Либо они должны поддерживть приращение, либо для них такой вариант создания неприменим. Не забываем про универсальность решения.

[IL_Agent]

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

Вот этот пункт явно указывает, что список у нас из чисел. А если объекты?

Да, пункты 3 и 4 заточены по числа. Видимо, с оглядкой на Хаскелевские [1,3 ..] Предлагаю так:
# 3) Создание списка бесконечного размера, заданного начальным значением и функцией приращения, обозначается list(elem, inc(elem):elem ), каждый последующий элемент является значением функции inc от предыдущего.
# 4) Создание списка, заданного начальным значениеv, функцией определения конца списка и функцией приращения, обозначается list(elem, is_end(elem):bool, inc(elem):elem).

[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

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

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