Вчера меня озадачили вопросом:
А как в .NET/C# реализовать знакомые всем функциональщикам примитивы cons, car и cdr. Причем вычисления должны быть линивыми, по возможности не типизированными.
Не обязательно LINQ, просто это первое что пришло в голову.
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
1
(car (cdr z))
3
Вот то, что получилось у меня на С#
using System;
using System.Collections.Generic;
using System.Linq;
namespace LinqCons
{
class Program
{
static void Main(string[] args)
{
var x = from value in new List<int> { 1, 2 } select value;
var y = from value in new List<int> { 3, 4 } select value;
var z = from value in new List<IEnumerable<int>> { x, y } select value;
Console.WriteLine(z.First().First()); // Prints 1
Console.WriteLine(z.Last().First()); // Prints 3
}
}
}
Но как-то оно коряво? и не уверен, что лениво. Эксперты, помогите, плз
Здравствуйте, SE, Вы писали:
SE>Вчера меня озадачили вопросом: SE>А как в .NET/C# реализовать знакомые всем функциональщикам примитивы cons, car и cdr. Причем вычисления должны быть линивыми, по возможности не типизированными. SE>Не обязательно LINQ, просто это первое что пришло в голову.
car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
Здравствуйте, gandjustas, Вы писали:
SE>>Не обязательно LINQ, просто это первое что пришло в голову.
G>car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, gandjustas, Вы писали:
SE>>>Не обязательно LINQ, просто это первое что пришло в голову.
G>>car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
L>причем тут кортежи?
cons создает кортеж.
Здравствуйте, gandjustas, Вы писали:
G>>>car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
L>>причем тут кортежи? G>cons создает кортеж.
Тогда First и Skip — неправильные ответы, т.к. они работают с последовательностями.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, SE, Вы писали:
SE>>Вчера меня озадачили вопросом: SE>>А как в .NET/C# реализовать знакомые всем функциональщикам примитивы cons, car и cdr. Причем вычисления должны быть линивыми, по возможности не типизированными. SE>>Не обязательно LINQ, просто это первое что пришло в голову.
G>car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
На самом деле обманул.
car — первый элемент кортежа, cdr — второй.
Так как в C# кортежей нет, то и аналогов нет.
Списки в lisp\scheme состоят из вложенных кортежей, поэтому применительно к спискам car — "голова", а cdr — "хвост".
В C# аналогично работают .First() и .Skip(1)
Здравствуйте, gandjustas, Вы писали:
SE>>>>Не обязательно LINQ, просто это первое что пришло в голову.
G>>>car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
L>>причем тут кортежи? G>cons создает кортеж.
Ну вот цель как раз хотя бы эмулировать в .NET кортежи, если уж их не имеется.
Здравствуйте, SE, Вы писали:
SE>А как в .NET/C# реализовать знакомые всем функциональщикам примитивы cons, car и cdr. Причем вычисления должны быть линивыми, по возможности не типизированными.
Вот что меня всегда рабодало в тру фанкшнал языках, так это понятные названия функций и переменных.
Здравствуйте, SE, Вы писали:
SE>Вчера меня озадачили вопросом: SE>А как в .NET/C# реализовать знакомые всем функциональщикам примитивы cons, car и cdr. Причем вычисления должны быть линивыми, по возможности не типизированными. SE>Не обязательно LINQ, просто это первое что пришло в голову.
SE>Вот пример на Scheme взятый из SICP, 2.1 Introduction to Data Abstraction:
В той же книге есть пример как сделать пару с помощью функций. Вот так оно выглядит на Lisp:
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Аргумент не 0 или 1 -- CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
А вот так оно выглядит на C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinqCons
{
class Program
{
static object cons(object x, object y)
{
Func<int, object> f = (m) => { return m == 0 ? x : y; };
return f;
}
static object car(object z)
{
return ((Func<int, object>)z)(0);
}
static object cdr(object z)
{
return ((Func<int, object>)z)(1);
}
static void Main(string[] args)
{
object x = cons(1, 2);
object y = cons(3, 4);
object z = cons(x, y);
x = car(cdr(z)); // 3
}
}
}
Спасибо
А теперь как бы еще повторить пример из SICP, который я привел в исходном собщении. Очевидно, что не хватает понятия пары в противовес последовательности.
Поясню: вложенный cons в Схеме дает ((1,2)(3,4)), в Линке (1,2,3,4). Соответсвенно, первый элемент во второй паре в Схеме — 3, в Линке на указанных аналогах операций — 2
Здравствуйте, SE, Вы писали:
SE>Здравствуйте, AndrewVK, Вы писали:
AVK>>cons : (x, y) => Enumerable.Repeat(x, 1).Concat(Enumerable.Repeat(y, 1)); AVK>>car : seq => seq.First() AVK>>cdr : seq => seq.Skip(1).First()
SE>Спасибо SE>А теперь как бы еще повторить пример из SICP, который я привел в исходном собщении. Очевидно, что не хватает понятия пары в противовес последовательности. SE>Поясню: вложенный cons в Схеме дает ((1,2)(3,4)), в Линке (1,2,3,4). Соответсвенно, первый элемент во второй паре в Схеме — 3, в Линке на указанных аналогах операций — 2
Наверное так:
var x = new[] {1,2};
var y = new[] {3,4};
var z = new[] {x,y};
//Ну дальше понятно
Здравствуйте, gandjustas, Вы писали:
G>car — .First(), cdr — Skip(1), cons не существует ибо нету кортежей.
Каких еще кортежей? Конс — это конструктор связанного списка. И вообще — это инструкции Лиспа по работе со связанными списками. Вот только Лисп на их базе все структуры данных строит. А в дотнете их даже нет. Вместо них используется IEnumerable<T> и итераторы ака yield.
Так что прямой ответ — нет таких фишек в дотнете и его библиотеках. Ну, а замена и правда может быть реализована на базе .First(), Skip(1) и итераторах. Вот только по жизни достаточно более высокоуровневых функций ака linq.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, gandjustas, Вы писали:
G>cons создает кортеж.
cons создает элементы списка. nil — это пустой списко, а cons — конструктор элемента списка. Его задача добавить новый элемент в конец существующего списка. Кортежей в Лиспе вообще нет, так как Лисп язык динамически типизированный.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, SE, Вы писали:
SE>А теперь как бы еще повторить пример из SICP, который я привел в исходном собщении. Очевидно, что не хватает понятия пары в противовес последовательности.
В линке есть анонимные типы
SE>Поясню: вложенный cons в Схеме дает ((1,2)(3,4)), в Линке (1,2,3,4).
Тот аналог cons, который привел я, дает IEnumerable<Ienumerable<T>>, т.е. как и в лиспе. А чтобы привести его ко второму виду, нужно позвать SelectMany().
Ну а аналог приведенного тобой кода, в том числе и с учетиом ленивости, будет как то так:
using System;
using System.Collections.Generic;
using System.Linq;
static class Program
{
static IEnumerable<T> Cons<T>(T x, T y)
{
yield return x;
yield return y;
}
static T Car<T>(this IEnumerable<T> src)
{
return src.First();
}
static T Cdr<T>(this IEnumerable<T> src)
{
return src.Skip(1).First();
}
static void Main()
{
var x = Cons(1, 2);
var y = Cons(3, 4);
var z = Cons(x, y);
Console.WriteLine(z.Car().Car());
Console.WriteLine(z.Cdr().Car());
}
}
... << RSDN@Home 1.2.0 alpha 4 rev. 1111 on Windows Vista 6.0.6001.65536>>
Здравствуйте, SE, Вы писали:
SE>А как в .NET/C# реализовать знакомые всем функциональщикам примитивы cons, car и cdr. Причем вычисления должны быть линивыми, по возможности не типизированными.
В общем-то нужны просто туплы:
public class Cons<TCar, TCdr>
{
public TCar car;
public TCdr cdr;
public Cons(TCar car, TCdr cdr)
{
this.car = car;
this.cdr = cdr;
}
public TCar Car
{
get { return this.car; }
}
public TCdr Cdr
{
get { return this.cdr; }
}
}
// Добавим вспомогательных функций чтобы было похоже на Scheme-ный синтаксисpublic static Cons<TCar, TCdr> Cons<TCar, TCdr>(TCar car, TCdr cdr)
{
return new Cons<TCar, TCdr>(car, cdr);
}
public static TCar Car<TCar, TCdr>(Cons<TCar, TCdr> cons)
{
return cons.Car;
}
public static TCdr Cdr<TCar, TCdr>(Cons<TCar, TCdr> cons)
{
return cons.Cdr;
}
static void Main(string[] args)
{
var x = Cons(1, 2);
var y = Cons(3, 4);
var z = Cons(x, y);
Console.WriteLine(Car(Car(z)));
Console.WriteLine(Car(Cdr(z)));
// Структуры в SICP-пе бывают довольно "древовдными"...var p = Cons(x, z);
Console.WriteLine(Car(Cdr(Cdr(p))));
}
Ленивость можно изобразить так же как оно сделано в SICP:
public class Lazy<T>
{
Func<T> calc;
public Lazy(Func<T> calc)
{
this.calc = calc;
}
public T Force()
{
return calc();
}
}
// Такие же модифицированные "stream"-операцииpublic static Cons<TCar, Lazy<TCdr>> ConsStream<TCar, TCdr>(TCar car, Lazy<TCdr> cdr)
{
return new Cons<TCar, Lazy<TCdr>>(car, cdr);
}
public static TCar CarStream<TCar, TCdr>(Cons<TCar, Lazy<TCdr>> cons)
{
return cons.Car;
}
public static TCdr CdrStream<TCar, TCdr>(Cons<TCar, Lazy<TCdr>> cons)
{
return cons.Cdr.Force();
}
// Определим и Stream тада уж (это, в общем-то синоним Cons<TCar, Lazy<TCdr>>, но добавим IEnumerable чтобы LINQ-ом можно было обрабатывать)public class Stream<T> : Cons<T, Lazy<Stream<T>>>, IEnumerable<T>
{
public Stream(T current, Lazy<Stream<T>> next)
: base(current, next)
{
}
#region IEnumerable<T> Members
public IEnumerator<T> GetEnumerator()
{
var current = this;
while(current != null)
{
yield return this.Car;
if (this.Cdr != null)
current = current.Cdr.Force();
}
}
#endregion
#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
}
public static Stream<int> EnumerateInterval(int from, int to)
{
return from <= to ?
new Stream<int>(from, new Lazy<Stream<int>>(() => EnumerateInterval(from + 1, to))) :
null;
}
static void Main(string[] args)
{
Console.WriteLine(EnumerateInterval(1, 5).Sum());
var interval = EnumerateInterval(1, int.MaxValue);
Console.WriteLine(interval.Take(10).Sum());
}
Получается конечно же просто переложение Scheme-вской имплементации ленивости — т.е. абсолютно неэффективное на С#
Здравствуйте, AndrewVK, Вы писали:
AVK>Вот что меня всегда рабодало в тру фанкшнал языках, так это понятные названия функций и переменных.
AVK>cons : (x, y) => Enumerable.Repeat(x, 1).Concat(Enumerable.Repeat(y, 1)); AVK>car : seq => seq.First() AVK>cdr : seq => seq.Skip(1).First()
Лисп как бы к фунциональным языкам имеет только то отношение, что он их породил. "тру фанкшнал" они никогда не был и никогда не будет.
Что до совершенно дурацких названий вроде car/cdr, тут свою роль с играла техника. Лисп ведь когда изобретался, то никакой терминологии еще не было. За-то была конкретная машина в который были две аппаратные инструкции car и cdr. Эти инструкции как раз позволяли реализовать (в одну инструкцию) извлечение значения первого элемента списка и получение ссылки на хвост списка. Ну, и товарищам ничего умнее в голову не пришло, чем тупо использовать название машинных команд для данных операций. "cons" имеет более разумное название, так как это функция консолидации, т.е. cons — это сокращение. Ее суть — добавление элемента в начало списка.
Так что все разумно. Ну, а в других ФЯ зачастую операции работы со списками имеют собственный синтаксис, так что в названиях вообще не нуждаются. Например, в Немерле получение головы списка производится или через свойство Head или с помощью паттерн-матчинга "firstElem :: _". Почти та же фигня во всех ML-клонах.
В прочем, с названиями в ФЯ действительно задница. Но она скорее наблюдается в программах на ФЯ, так как они зачастую пишутся в "математическом стиле" с однобуквенными, абстрактными именами переменных.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
SE>(define x (cons 1 2))
SE>(define y (cons 3 4))
SE>(define z (cons x y))
SE>(car (car z))
SE>1
SE>(car (cdr z))
SE>3
SE>
В C# нет полных аналогов списков Лиспа. Так что полный аналог создать трудно. Точнее если ты реализуешь однонаправленный свяазанный список, то получишь полную копию (ну, может шума синтаксическго по больше будет). Но в принципе аналогом тут можно считать работу с последовательностями.
Напиши аналог cons из Лиспа и твои примеры будут выглядеть точно так же (с поправкой на синтаксис C#):
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
public static IEnumerable<T> Cons<T>(T value1, T value2)
{
yield return value1;
yield return value2;
}
static void Main()
{
var x = Cons(1, 2);
var y = Cons(3, 4);
var z = Cons(x, y);
Console.WriteLine(z.First().First());
Console.WriteLine(z.Last().First());
}
}
Выводит точно так же:
1
3
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Небольшая поправочка. Cdr в Лиспе возвращает хвост списка. Просто в приведенном примере в хвосте остается только один элемент. Так что реализовывать его надо просто как Skip(1).
Проблема еще в том, что в Лиспе при выводе на консоль списка выводятся его значении, а в дотнете дурацкое имя класса итератора. Так что еще нужно писать свой аналог принта.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, gandjustas, Вы писали:
G>>cons создает кортеж.
VD>cons создает элементы списка. nil — это пустой списко, а cons — конструктор элемента списка. Его задача добавить новый элемент в конец существующего списка.
(cons x y), где x и y не nil, что создает? Список? А где его конец? Можно ли для него применить fold?
Тем не менее это вполне корректное выражение и создает корректный результат.
VD>Кортежей в Лиспе вообще нет, так как Лисп язык динамически типизированный.
Разве это мешает кортежам?
Здравствуйте, VladD2, Вы писали:
VD>Небольшая поправочка. Cdr в Лиспе возвращает хвост списка.
Не хвост, а именно что второй элемент.
С хвостом проще, есть готовый метод Last.
VD> Просто в приведенном примере в хвосте остается только один элемент. Так что реализовывать его надо просто как Skip(1).
Просто Skip(1) возвращает IEnumerable<T>, а не Т
VD>Проблема еще в том, что в Лиспе при выводе на консоль списка выводятся его значении, а в дотнете дурацкое имя класса итератора.
Это не проблема, если речь идет не о написании книжки.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111 on Windows Vista 6.0.6001.65536>>
Здравствуйте, VladD2, Вы писали:
VD>cons создает элементы списка. nil — это пустой списко, а cons — конструктор элемента списка. Его задача добавить новый элемент в конец существующего списка. Кортежей в Лиспе вообще нет, так как Лисп язык динамически типизированный.
Сори, конечно же в начало списка, так как однонаправленные связанные списки вставляют элементы в начало списка.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, gandjustas, Вы писали:
VD>>cons создает элементы списка. nil — это пустой списко, а cons — конструктор элемента списка. Его задача добавить новый элемент в конец существующего списка.
G>(cons x y), где x и y не nil, что создает? Список? А где его конец? Можно ли для него применить fold? G>Тем не менее это вполне корректное выражение и создает корректный результат.
Да, согласен. Тут я гоню. Список это конечно же частный случай. Но и кортежем это ни как не является. Если только частным случаем — парой.
Создать кортеж из 3 элементов уже не удастся. Точнее чтобы объединить более одного элемента используются ссылки, так что по любому выходит список или дерево.
VD>>Кортежей в Лиспе вообще нет, так как Лисп язык динамически типизированный. G>Разве это мешает кортежам?
Мх. Наверно это зависит от определения. Я видимо привык к определению кортежей из статически типизированных языков.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
VD>>Небольшая поправочка. Cdr в Лиспе возвращает хвост списка.
AVK>Не хвост, а именно что второй элемент.
Не. Для списков возвращается именно что хвост. Просто в примере как раз не список. Тут я ошибся. В примере пара числел и пара пар чисел. Так что cdr действительно вынимает целое. Но это не элемент, а значение.
AVK>С хвостом проще, есть готовый метод Last.
На самом деле данный пример просто не выражается последовательностями. Я, честно говоря, сильно подзабыл Лисп. Не знаю только огорчает меня это или радует .
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
G>>cons создает кортеж.
VD>cons создает элементы списка. nil — это пустой списко, а cons — конструктор элемента списка. Его задача добавить новый элемент в конец существующего списка. Кортежей в Лиспе вообще нет, так как Лисп язык динамически типизированный.
Подумал по шипче и понял, что гоню. cons двух атомов создает нечто вроде пары, что действительно можно выразить чем-то вроде класса с двумя полями. Но назвать частный случай "пару" общим словом "кортеж", у меня все равно рука не поворачивается.
Здравствуйте, AndrewVK, Вы писали:
AVK>Ты это всерьез?
Для тех кто подзабыл Лисп напоминаю, что cons/car/cdr в нем используются для создания/работы со структурами не только типа "однотипный список", но и с любыми другими (в частности с иерархическими или, скажем, списками неоднородных элементов). Автор топика хотел увидеть имплементация именно базовых cons/car/cdr, а не случай их частного применения к однородному списку.
Hint: Попробуй проверить свое решение на вот таком расширенным примере:
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(define p (cons x z))
(car (car z))
1
(car (cdr z))
3
(car (cdr (cdr p)))
3
...при помощи базового cons можно создавать и такие структуры:
PS Ленивые cons/cdr в SICP тоже хороше разжеваны: 3.5 Streams
Здравствуйте, <Аноним>, Вы писали:
А>Для тех кто подзабыл Лисп напоминаю, что cons/car/cdr в нем используются для создания/работы со структурами не только типа "однотипный список", но и с любыми другими (в частности с иерархическими или, скажем, списками неоднородных элементов). Автор топика хотел увидеть имплементация именно базовых cons/car/cdr, а не случай их частного применения к однородному списку.
Голову включать тоже при этом стоит. Иначе действительно для решения примитивной задачи понадобится несколько экранов кода.
А>Hint: Попробуй проверить свое решение на вот таком расширенным примере:
Правильно, потому что лисп динамический язык. И твой вариант просто имитирует внешние эффекты, реально отличаясь от лиспа еще больше. На C# 4, возможно, получится действительно сделать более похоже, но смысла в этом ноль.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111 on Windows Vista 6.0.6001.65536>>
Простейшая реализация примитивов Cons, Car, Cdr и List. Правда без Линка и ленивости, но зато видно, как устроены Лисповские списки изнутри. Просто тут в ветке вижу у людей путаница со списками. А вся правда в том, что в Лиспе нет списков, а есть пары и на основе пар, строятся списки, вот пример:
class ConsObj
{
public object First { get; private set; }
public object Second { get; private set; }
public ConsObj(object a, object b)
{
First = a;
Second = b;
}
}
class Program
{
static object Cons(object a, object b)
{
return new ConsObj(a, b);
}
static object Car(object a)
{
return ((ConsObj)a).First;
}
static object Cdr(object a)
{
return ((ConsObj)a).Second;
}
static object List(params object[] l)
{
if (l.Length == 1)
return Cons(l[0], null);
else
{
object[] last = new object[l.Length - 1];
for (int i = 1; i < l.Length; i++)
last[i - 1] = l[i];
return Cons(l[0], List(last));
}
}
static void Main(string[] args)
{
object l = List(1, 2, 3);
object f = Car(l);
object s = Car(Cdr(l));
object t = Car(Cdr(Cdr(l)));
Console.WriteLine(f + " " + s + " " + t);
}
}
Lisp is not dead. It’s just the URL that has changed: http://clojure.org
Здравствуйте, VladD2, Вы писали:
L>>Не так. cons зосздает пару, а пара является списком только в том случае, если второй элемент — nil или список.
VD>Прежде чем отвечать прочти всю тему: http://rsdn.ru/forum/message/3141182.1.aspx
L>>И что это изменит? После почтения cons как не создавал список, так его и не создает.
VD>Извини, я не подумал. Это действительно ничего в тебе не меняет.
При чем тут я-то? Я не о себе говорю, а о твоей фразе:
Конс — это конструктор связанного списка.
Она вне зависимости от того, изменится что-либо во мне или нет, останется неверной.
L>>>И что это изменит? После почтения cons как не создавал список, так его и не создает. VD>>Извини, я не подумал. Это действительно ничего в тебе не меняет. L>При чем тут я-то? Я не о себе говорю, а о твоей фразе:
L>Конс — это конструктор связанного списка.
L>Она вне зависимости от того, изменится что-либо во мне или нет, останется неверной.
Да просто Влад уже осознал (в том топике, ссылку на который привёл), "что гонит", за девятнадцать часов до твоей поправки
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
L>>Она вне зависимости от того, изменится что-либо во мне или нет, останется неверной.
_FR>Да просто Влад уже осознал (в том топике, ссылку на который привёл), "что гонит", за девятнадцать часов до твоей поправки
Наконец-то выдалась минутка написать код. Получилось без LINQ, совсем не лениво, ну и ладно. Зато без явного приведения типов.
using System;
namespace ConsTest
{
class Program
{
static void Main(string[] args)
{
var x = Cons.Create(1, 2);
var y = Cons.Create(3, 4);
var z = Cons.Create(x, y);
Console.WriteLine(z.Car.Car); // 1
Console.WriteLine(z.Cdr.Car); // 3
}
}
public class Cons<T1, T2>
{
public Cons(T1 car, T2 cdr)
{
Car = car;
Cdr = cdr;
}
public T1 Car { get; private set; }
public T2 Cdr { get; private set; }
}
public class Cons
{
public static Cons<T1, T2> Create<T1,T2>(T1 car, T2 cdr)
{
return new Cons<T1, T2>(car, cdr);
}
}
}
P.S. Вот, изучу линк как следует, тогда еще попробую
P.P.S. Да, классы назвал одинаково — фантазию заклинило
