Вчера меня озадачили вопросом:
А как в .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>Кортежей в Лиспе вообще нет, так как Лисп язык динамически типизированный.
Разве это мешает кортежам?
