Este é um bom exercício para se tornar mais fluente na linguagem de programação que você pretende aprender, mas que apenas mexeu levemente. Isso envolve trabalhar com objetos, usar ou simular fechamentos e esticar o sistema de tipos.

Sua tarefa é escrever código para gerenciar listas preguiçosas e usá-lo para implementar esse algoritmo para gerar números de Fibonacci:

As amostras de código estão em Haskell

let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 in take 40 fibs

Resultado:

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]

Sua implementação de lista lenta deve atender a estas diretrizes:

• Um nó da lista é uma das três coisas:
  • Nil - lista vazia.
    []
  • Contras - Um único item, emparelhado com uma Lista dos itens restantes:
    1 : [2,3,4,5]
    ( :é o operador contras em Haskell)
  • Thunk - Uma computação adiada que produz um nó de Lista quando necessário.
• Ele suporta as seguintes operações:
  • nil - Construa uma lista vazia.
  • contras - Construa uma célula contras.
  • thunk - Construa um Thunk, dada uma função que não aceita argumentos e retorna Nil ou Contras.
  • force - Dado um nó de lista:
    • Se for Nil ou Contras, basta devolvê-lo.
    • Se for um Thunk, chame sua função para obter Nil ou Cons. Substitua o thunk por Nil ou Cons e devolva-o.
      Nota: A substituição da conversão por seu valor forçado é uma parte importante da definição de "preguiçoso" . Se esta etapa for ignorada, o algoritmo Fibonacci acima será muito lento.
  • vazio - Veja se um nó da Lista é Nil (depois de forçá-lo).
  • head (aka "car") - Pegue o primeiro item de uma lista (ou ajuste se for Nil).
  • tail (aka "cdr") - Obtenha os elementos após o cabeçalho de uma lista (ou ajuste se for Nil).
  • zipWith - Dada uma função binária (por exemplo (+)) e duas listas (possivelmente infinitas), aplique a função aos itens correspondentes das listas. Exemplo:
    zipWith (+) [1,2,3] [1,1,10] == [2,3,13]
    
  • take - Dado um número N e uma lista (possivelmente infinita), pegue os primeiros N itens da lista.
  • imprimir - Imprima todos os itens de uma lista. Isso deve funcionar de maneira incremental quando é fornecida uma lista longa ou infinita.

• fibsusa-se em sua própria definição. Configurar recursão lenta é um pouco complicado; você precisará fazer algo assim:

  • Aloque um thunk para fibs. Deixe-o em um estado fictício por enquanto.
  • Defina a função thunk, que depende de uma referência a fibs.
  • Atualize o thunk com sua função.

  Você pode ocultar esse encanamento definindo uma função fixque chama uma função de retorno de lista com seu próprio valor de retorno. Considere tirar um cochilo curto para que essa ideia possa surgir.

• O polimorfismo (a capacidade de trabalhar com listas de qualquer tipo de item) não é necessário, mas veja se você consegue encontrar uma maneira de fazer isso que seja idiomática no seu idioma.

• Não se preocupe com o gerenciamento de memória. Mesmo os idiomas com coleta de lixo tendem a carregar objetos que você nunca mais usará (por exemplo, na pilha de chamadas), portanto, não se surpreenda se o seu programa perder memória ao percorrer uma lista infinita.

Sinta-se à vontade para se afastar um pouco dessas diretrizes para acomodar os detalhes do seu idioma ou para explorar abordagens alternativas às listas preguiçosas.

Regras:

• Escolha um idioma que você não conhece bem. Não posso "exigir" isso, daí a tag "sistema de honra". No entanto, os eleitores podem verificar seu histórico para ver em quais idiomas você está postando.

• Não use o suporte à lista lenta do seu idioma para fazer tudo. Poste algo substancial ou pelo menos interessante.

  • Haskell está praticamente fora. Ou seja, a menos que você faça algo assim:

    data List a = IORef (ListNode a)
    data ListNode a = Nil | Cons !a !(List a) | Thunk !(IO (ListNode a))
    

    Nota: A avaliação não estrita de Haskell não está fora dos limites, mas sua implementação de lista lenta não deve derivar sua capacidade diretamente a partir daí. De fato, seria interessante ver uma solução eficiente e puramente funcional que não exija preguiça.

  • Python:

    • Não use ferramentas.
    • Os geradores são bons, mas, se você os usar, precisará encontrar uma maneira de memorizar valores forçados.

PostScript

Já toquei com PostScript antes , mas não diria que o conheço particularmente bem (na verdade, meu palpite é que você pode contar o número de pessoas no mundo que realmente conhecem o PostScript usando uma mão).

Eu me desviei das suas especificações, pois a função usada para criar um thunk pode retornar outro thunk; forcecontinuará avaliando até que o resultado seja a nilou a cons.

As listas são implementadas como dicionários:

<< /type /nil >>

<< /type /cons
   /head someValue
   /tail someList >>

<< /type /thunk
   /func evaluationFunction >>

<< /type /dataThunk
   /func evaluationFunction
   /data someValueToBePassedToTheFunction >>

O código a seguir. Observe que estamos substituindo alguns operadores internos (em particular print; não verifiquei se há mais); no uso no mundo real, isso teria que ser observado. Claro que não haverá uso no mundo real, então tudo bem.

Os comentários antes dos procedimentos devem ser lidos como

% before2 before1 before0  <| procedure |>  after1 after0

ou seja, mostrando o conteúdo esperado da pilha antes da chamada e o conteúdo resultante da pilha após a chamada. Os comentários dentro dos procedimentos mostram o conteúdo da pilha após a execução da linha específica.

% Helper procedure that creates a dictionary with the top two elements as keys
% and the next two elements as values.
%
% value1 value2 key1 key2  <| _twodict |>  << /key1 /value1 /key2 /value2 >>
/_twodict {
    << 5 1 roll    % << value1 value2 key1 key2
    4 2 roll       % << key1 key2 value1 value2
    3 2 roll       % << key1 value1 value2 key2
    exch >>
} def

/nil {
    << /type /nil >>
} def

% item list  <| cons |>  consCell
/cons {
    /head /tail _twodict
    dup /type /cons put
} def

% constructs a thunk from the function, which will be called with no
% arguments to produce the actual list node. It is legal for the function
% to return another thunk.
%
% func  <| thunk |>  lazyList
/thunk {
    /thunk /func /type _twodict
} def

% A dataThunk is like a regular thunk, except that there's an additional
% data object that will be passed to the evaluation function
%
% dataObject func  <| dataThunk |>  lazyList
/dataThunk {
    /data /func _twodict
    dup /type /dataThunk put 
} def

% lazyList  <| force |>  consOrNil
/force {
    dup /type get dup
    /thunk eq
    {
        pop
        dup /func get exec exch copy
        force
        dup /func undef
    }
    {
        /dataThunk eq
        {
            dup dup /data get exch
            /func get exec exch copy
            force
            dup dup /func undef /data undef
        } if
    } ifelse
} def

/empty {
    force
    /type get
    /nil eq
} def

/head {
    force /head get
} def

/tail {
    force /tail get
} def

/print {
    dup empty not
    {
        dup
        head ==
        tail
        print    
    }
    {
        pop
    } ifelse
} def

% sourceList n  <| take |>  resultingList
/take {
    /source /n _twodict
    {
        dup /source get exch    % source data
        /n get 1 sub dup        % source n-1 n-1
        -1 eq
        {
            pop pop nil
        }
        {                       % source n-1
            exch                % n-1 source
            dup head            % n-1 source head
            3 1 roll            % head n-1 source
            tail
            exch take           % head rest
            cons
        } ifelse
    }
    dataThunk
} def

% sourceList1 sourceList2 func  <| zipWith |>  resultList
/zipWith {
    3 1 roll
    2 array astore                  % func [L1 L2] 
    /func /sources _twodict
    {
        dup /sources get aload pop  % data L1 L2
        2 copy empty exch empty or
        {
            pop pop pop nil
        }
        {
            dup head exch tail      % data L1 H2 T2
            3 2 roll
            dup head exch tail      % data H2 T2 H1 T1
            exch                    % data H2 T2 T1 H1
            4 3 roll                % data T2 T1 H1 H2
            5 4 roll /func get      % T2 T1 H1 H2 func
            dup 4 1 roll            % T2 T1 func H1 H2 func
            exec                    % T2 T1 func NEWHEAD
            4 2 roll                % func NEWHEAD T2 T1
            exch 4 3 roll           % NEWHEAD T1 T2 func 
            zipWith cons
        } ifelse
    }
    dataThunk
} def

Carregue isso no Ghostscript, ignorando a página exibida - estamos trabalhando apenas com o intérprete. Aqui está o algoritmo de Fibonacci:

[balpha@localhost lazylist]$ gs lazylist.ps 
GPL Ghostscript 8.71 (2010-02-10)
Copyright (C) 2010 Artifex Software, Inc.  All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
GS> /fibs 0 1 { fibs fibs tail { add } zipWith } thunk cons cons def
GS> fibs 40 take print
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
GS>

Duas funções interessantes adicionais:

% creates an infinite list that starts with the given value, incrementing
% by one for each additional element
%
% startValue  <| count |>  lazyList
/count {
    {
        dup
        1 add count
        cons
    }
    dataThunk
} def    

% apply the given function to each element of the source list, creating
% a (lazy) list that contains the corresponding results
%
% sourceList function  <| map |> resultList
/map {
    /source /func _twodict
    {
        dup /func get exch
        /source get                 % func source
        dup empty not
        {
            dup head                % func source head
            2 index                 % func source head func
            exec 3 1 roll           % newHead func source
            tail exch map cons
        }
        {
            pop pop nil
        } ifelse
    }
    dataThunk
} def

Comece a contar com 5, multiplique cada elemento da lista resultante por 3 e exiba os dez primeiros valores:

GS> 5 count { 3 mul } map 10 take print
15
18
21
24
27
30
33
36
39
42

Sobre o polimorfismo: Embora o PostScript seja fortemente digitado, ele permite tipos arbitrários como valores de dicionário, para que você possa inserir o que quiser:

GS> 1337 [ 42 3.14 ] << /key /value >> (Hello world) 3 count
GS<5> cons cons cons cons 10 take print
1337
[42 3.14]
-dict-
(Hello world)
3
4
5
6
7
8
GS>

Observe que erros de tipo, por exemplo, ao tentar adicionar strings a números, ocorrerão apenas no momento da avaliação:

GS> (some string) (another string) nil cons cons
GS<1> 13 27 nil cons cons
GS<2> { add } zipWith      % no error yet
GS<1> print
Error: /typecheck in --add--

C

Eu sou totalmente iniciante em C, esse código é realmente a primeira coisa real que codifiquei em C. Ele compila sem nenhum aviso e funciona bem no meu sistema.

Como construir

Primeiro, pegue o tarball do meu servidor . Ele inclui um makefile; portanto, basta executar makepara compilá-lo e depois make runexecutá-lo. O programa imprime uma lista dos primeiros 93 números de fibonacci. (Após o número 94, um número inteiro de 64 bits sem sinal transborda)

Explicação

O núcleo do programa é o arquivo lazy-list.c. No arquivo de cabeçalho correspondente, defino uma estrutura list, que é a nossa lista lenta. Se parece com isso:

enum cell_kind {
  NIL,
  CONS,
  THUNK
};

typedef enum cell_kind cell_kind;

typedef long int content_t;

struct list {
  cell_kind kind;
  union {
    struct {
      content_t* head;
      struct list* tail;
    } cons;
    struct {
      struct list* (*thunk)(void*);
      /* If you want to give arguments to the thunk, put them in here */
      void* args;
    } thunk;
  } content;
};

O membro kindé uma espécie de tag. Ele marca, se reciclamos as listas end ( NIL), uma célula que já está avaliada ( CONS) ou uma conversão ( THUNK). Então, segue-se uma união. Isto é

• uma célula já avaliada com um valor e uma cauda
• ou um thunk, apresentando um ponteiro de função e uma estrutura, que podem conter alguns argumentos para a função, se necessário.

O conteúdo da união é afirmado pela tag. Se a tag for NIL, o conteúdo da união é indefinido.

Ao definir as funções auxiliares mencionadas na especificação acima, geralmente é possível abstrair a definição de lista de seu uso, por exemplo. você pode simplesmente ligar nil()para obter uma lista vazia em vez de criar uma sozinha.

As três funções mais interessantes são zipWith, takee fibonaccis. Mas não quero explicar take, pois é muito parecido com zipWith. Todas as funções, que operam preguiçosamente, têm três componentes:

• Um invólucro, que cria uma conversão
• Um trabalhador que executa os cálculos para uma célula
• Uma estrutura que mantém os argumentos

No caso de zipWith, estes são zipWith, __zipWithe __zipArgs. Eu apenas os mostro aqui, sem mais explicações, a função deve ser bem clara:

struct __zipArgs {
  content_t* (*f)(content_t*,content_t*);
  list* listA;
  list* listB;
};

static list* __zipWith(void* args_) {
  struct __zipArgs* args = args_;
  list* listA = args->listA;
  list* listB = args->listB;
  list* listC;

  content_t* (*f)(content_t*,content_t*) = args->f;
  content_t* headA = head(listA);
  content_t* headB = head(listB);
  content_t* headC;

  if (NULL == headA || NULL == headB) {
    free(args);
    return nil();
  } else {
    headC = f(headA, headB);
    args->listA = tail(listA);
    args->listB = tail(listB);
    listC = thunk(__zipWith,args);
    return cons(headC,listC);
  }
}

list* zipWith(content_t* (*f)(content_t*,content_t*),list* listA, list* listB) {
  struct __zipArgs* args = malloc(sizeof(struct __zipArgs));
  args->f = f;
  args->listA = listA;
  args->listB = listB;
  return thunk(__zipWith,args);
}

A outra função interessante é fibonaccis(). O problema é que precisamos passar um ponteiro da primeira e da segunda célula para a thunk da terceira, mas, para criar essas células, também precisamos de um ponteiro para a thunk. Para resolver esse problema, preenchi o ponteiro do thunk com um NULLprimeiro e o troquei para thunk, depois que ele foi criado. Aqui está a escuta:

static content_t* __add(content_t* a,content_t* b) {
  content_t* result = malloc(sizeof(content_t));
  *result = *a + *b;
  return result;
}

list* fibonaccis() {
  static content_t one_ = 1;
  static content_t zero_ = 0;
  list* one  = cons(&one_,NULL);
  list* two  = cons(&zero_,one);
  list* core = zipWith(__add,one,two);
  one->content.cons.tail = core;
  return two;

Possíveis melhorias

• Minha solução não usa polimorfismo. Embora possível, minhas habilidades em C não são suficientes para saber como usá-lo. Em vez disso, usei um tipo content_t, que pode ser alterado para o que couber.
• Pode-se extrair o thunk da definição da lista e usá-lo apenas de maneira abstrata, mas isso tornaria o código mais complicado.
• Pode-se melhorar as partes do meu código que não são boas C.

C ++

Esta é a maior coisa que eu já escrevi em C ++. Eu normalmente uso Objective-C.

É polimórfico, mas nunca libera nada.

Minha mainfunção (e a addfunção to ZipWith) acabou assim:

int add(int a, int b) {return a + b;}

int main(int argc, char **argv) {
    int numFib = 15; // amount of fibonacci numbers we'll print
    if (argc == 2) {
        numFib = atoi(argv[1]);
    }

    // list that starts off 1, 1...
    LazyList<int> fibo = LazyList<int>(new Cons<int>(1,
                     new LazyList<int>(new Cons<int>(1))));
    // zip the list with its own tail
    LazyList<int> *fiboZip = LazyList<int>::ZipWith(add, &fibo, fibo.Tail());
    // connect the begin list to the zipped list
    fibo.Tail() -> ConnectToList(fiboZip);

    // print fibonacci numbers
    int *fibonums = fibo.Take(numFib);    
    for (int i=0; i<numFib; i++) cout << fibonums[i] << " ";

    cout<<endl;

    return 0;
}

Isto dá

 ./lazylist-fibo 20
 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 

As classes funcionam assim:

make a thunk:    LazyList<T>(new Thunk<T>( function, *args )) 
make empty list: LazyList<T>(new Nil<T>())
make cons:       LazyList<T>(new Cons<T>( car, *cdr ))

list empty:      list.Empty()
list's head:     list.Head()
list's tail:     list.Tail()
zipWith:         LazyList<T>::ZipWith(function, a, b)
take:            list.Take(n)
print:           list.Print()

Fonte completa: aqui . É uma bagunça, principalmente porque está em um arquivo grande.

Edit: mudou o link (o antigo estava morto).

Python

Não usa geradores para implementar a lista, apenas para implementar o __iter__método para uso com for.

class Node(object):
    def __init__(self, head, tail):
        self.__head__ = head
        self.__tail__ = tail

    def force(self):
        return self

    def empty(self):
        return False

    def head(self):
        return self.__head__

    def tail(self):
        return self.__tail__

    def zip_with(self, func, other):
        def gen_func():
            if other.empty():
                return other
            return Node(func(self.head(), other.head()), self.tail().zip_with(func, other.tail()))
        return Thunk(gen_func)

    def __iter__(self):
        while not self.empty():
            yield self.head()
            self = self.tail()

    def append(self, other):
        while not self.tail().empty():
            self = self.tail()
        self.__tail__ = other

    def take(self, n):
        if n == 0:
            return NullNode()
        else:
            return Node(self.__head__, self.__tail__.take(n - 1))

    def _print(self):
        for item in self:
            print item

class NullNode(Node):
    def __init__(self):
        pass

    def empty(self):
        return True

    def head(self):
        raise TypeError("cannot get head of nil")

    def tail(self):
        raise TypeError("cannot get tail of nil")

    def zip_with(self, func, other):
        return self

    def append(self, other):
        raise TypeError("cannot append to nil")

    def take(self, n):
        return self

class Thunk(Node):
    def __init__(self, func):
        self.func = func

    def force(self):
        node = self.func()
        self.__class__ = node.__class__
        if not node.empty():
            self.__head__ = node.head()
            self.__tail__ = node.tail()
        return self

    def empty(self):
        return self.force().empty()

    def head(self):
        return self.force().head()

    def tail(self):
        return self.force().tail()

    def take(self, n):
        return self.force().take(n)

A lista de Fibonacci é criada assim:

>>> from lazylist import *
>>> fib = Node(0, Node(1, NullNode()))
>>> fib.append(fib.zip_with(lambda a, b: a + b, fib.tail()))
>>> 

Rubi

Meu primeiro programa Ruby. Representamos todos os nós como matrizes, em que o comprimento da matriz determina o tipo:

0: empty list
1: thunk (call the single element to get the cons cell)
2: cons cell (1st is head, 2nd is tail)

O código é bastante simples, com um hack para redefinir a função thunk para configurar a fib recursiva.

def nil_()
  return Array[]
end

def cons(a, b)
  return Array[a, b]
end

def thunk(f)
  return Array[f]
end

def force(x)
  if x.size == 1
    r = x[0].call
    if r.size == 2
      x[0] = r[0]
      x.push(r[1])
    else
      x.pop()
    end
  end
end

def empty(x)
  force(x)
  return x.size == 0
end

def head(x)
  force(x)
  return x[0]
end

def tail(x)
  force(x)
  return x[1]
end

def zipWith(f, a, b)
  return thunk(lambda {
    if empty(a) or empty(b)
      return nil_()
    else
      return cons(f.call(head(a), head(b)), zipWith(f, tail(a), tail(b)))
    end
  })
end

def take(n, x)
  if n == 0
    return nil_()
  else
    return cons(head(x), take(n - 1, tail(x)))
  end
end

def print(x)
  while not empty(x)
    puts x[0]
    x = x[1]
  end
end

def add(x, y)
  return x + y
end

T=thunk(nil)  # dummy thunk function
fibs=cons(0, cons(1, T))
T[0]=zipWith(method(:add), fibs, tail(fibs))[0]  # overwrite thunk function

print(take(40, fibs))

Google Go

Um idioma relativamente novo, e eu aprendi usando CTRL+Fo Spec .

package main
import "fmt"

type List struct {
  isNil, isCons, isThunk bool
  head *interface { }
  tail *List
  thunk (func() List)
}

func Nil() List {
  return List { true, false, false, nil, nil, Nil }
}

func Cons(a interface { }, b List) List {
  return List { false, true, false, &a, &b, Nil }
}

func Thunk(f(func() List)) List {
  return List { false, false, true, nil, nil, f }
}

func Force(x List) List {
  if x.isNil { return Nil()
  } else if x.isCons { return Cons(*x.head, *x.tail) }
  return Force(x.thunk())
}

func Empty(x List) bool {
  return Force(x).isNil;
}

func Head(x List) interface { } {
  y := Force(x)
  if y.isNil { panic("No head for empty lists.") }
  return *y.head
}

func Tail(x List) List {
  y := Force(x)
  if y.isNil { panic("No tail for empty lists.") }
  return *y.tail
}

func Take(n int, x List) List {
  if (n == 0) { return Nil() }
  return Thunk(func() List {
    y := Force(x)
    return Cons(*y.head, Take(n - 1, *y.tail))
  })
}

func Wrap(x List) List {
  return Thunk(func() List {
    return x
  })
}

func ZipWith(f(func(interface { }, interface { }) interface { }), a List, b List) List {
  return Thunk(func() List {
    x, y := Force(a), Force(b)
    if x.isNil || y.isNil {
      return Nil()
    }
    return Cons(f(*x.head, *y.head), ZipWith(f, *x.tail, *y.tail))
  });
}

func FromArray(a []interface { }) List {
  l := Nil()
  for i := len(a) - 1; i > -1; i -- {
    l = Cons(a[i], l)
  }
  return l
}

func Print(x List) {
  fmt.Print("[")
  Print1(x)
  fmt.Print("]")
}

func Print1(x List) {
  y := Force(x)
  if y.isCons {
    fmt.Print(Head(y))
    z := Force(Tail(y))
    if z.isCons { fmt.Print(", ") }
    Print1(z)
  }
}

func Plus(a interface { }, b interface { }) interface { } {
  return a.(int) + b.(int)
}

func Fibs() List {

  return Thunk(func() List {
    return Cons(0, Cons(1, Thunk(func() List {
      return ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs)))
    })))
  })
}

func Fibs0() List {
  // alternative method, working
  return Cons(0, Cons(1, Fibs1(0, 1)))
}

func Fibs1(a int, b int) List {
  c := a + b
  return Cons(c, Thunk(func() List { return Fibs1(b, c) }))
}

func CountUp(x int, k int) List {
  return Cons(x, Thunk(func() List {
    return CountUp(x + k, k)
  }))
}

func main() {
  //a := []interface{} { 0, 1, 2, 3 }
  //l, s := FromArray(a), FromArray(a)
  Print(Take(40, Fibs()))
}

O problema foi resolvido, lidando com thunk-inside-a-thunks. No entanto, parece que o compilador online não pode receber 40 elementos, talvez por causa da memória. Vou testá-lo no meu Linux mais tarde.

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368runtime: address space conflict: map() = 
throw: runtime: address space conflict

panic during panic

Testei o código com o compilador online , porque não consigo instalar o Go on Windows facilmente.

Cristal

Apesar de seguir o repositório GitHub, nunca usei o Crystal até agora. Crystal é uma variante Ruby de tipo estatístico com inferência de tipo completo. Embora já haja uma resposta Ruby, a digitação estática de Crystal me levou a usar o polimorfismo, em vez de uma matriz, para representar os nós. Como o Crystal não permite modificações self, eu criei uma classe de invólucro denominada Nodeque envolveria todo o resto e gerenciaria os thunks.

Junto com as aulas, eu criei as funções de construtor lnil, conse thunk. Eu nunca usei Ruby para mais de um script de 20 linhas antes, também, então o material do bloco me assustou bastante.

Baseei a fibfunção na resposta Go .

class InvalidNodeException < Exception
end

abstract class LazyValue
end

class LNil < LazyValue
    def empty?
        true
    end

    def force!
        self
    end

    def head
        raise InvalidNodeException.new "cannot get head of LNil"
    end

    def tail
        raise InvalidNodeException.new "cannot get tail of Nil"
    end

    def take(n)
        Node.new self
    end
end

class Cons < LazyValue
    def initialize(@car, @cdr)
    end

    def empty?
        false
    end

    def force!
        @cdr.force!
        self
    end

    def head
        @car
    end

    def tail
        @cdr
    end

    def take(n)
        Node.new n > 0 ? Cons.new @car, @cdr.take n-1 : LNil.new
    end
end

class Thunk < LazyValue
    def initialize(&@func : (-> Node))
    end

    def empty?
        raise Exception.new "should not be here!"
    end

    def force!
        @func.call()
    end

    def head
        self.force!.head
    end

    def tail
        self.force!.tail
    end

    def take(n)
        self.force!.take n
    end
end

class Node
    def initialize(@value = LNil.new)
    end

    def empty?
        self.force!
        @value.empty?
    end

    def force!
        @value = @value.force!
        self
    end

    def head
        self.force!
        @value.head
    end

    def tail
        self.force!
        @value.tail
    end

    def take(n)
        self.force!
        return @value.take n
    end

    def print
        cur = self
        while !cur.empty?
            puts cur.head
            cur = cur.tail
        end
    end
end

def lnil
    Node.new LNil.new
end

def cons(x, r)
    Node.new Cons.new x, r
end

def thunk(&f : (-> Node))
    Node.new Thunk.new &f
end

def inf(st=0)
    # a helper to make an infinite list
    f = ->() { lnil }
    f = ->() { st += 1; cons st, thunk &f }
    thunk { cons st, thunk &f }
end

def zipwith(a, b, &f : Int32, Int32 -> Int32)
    thunk { a.empty? || b.empty? ? lnil :
            cons f.call(a.head, b.head), zipwith a.tail, b.tail, &f }
end

def fibs
    # based on the Go answer
    fibs2 = ->(a : Int32, b : Int32) { lnil }
    fibs2 = ->(a : Int32, b : Int32) { cons a+b, thunk { fibs2.call b, a+b } }
    cons 0, cons 1, thunk { fibs2.call 0, 1 }
end

fibs.take(40).print
zipwith(inf, (cons 1, cons 2, cons 3, lnil), &->(a : Int32, b : Int32){ a+b }).print

Inclinei um pouco as regras porque ainda não há uma solução .NET aqui - ou mais geralmente uma solução OOP, exceto a do Python que usa herança, mas é diferente o suficiente da minha solução para tornar as duas interessantes (em particular desde o Python permite modificar a selfinstância, tornando a implementação de thunk simples).

Então, isso é c # . Divulgação completa: não estou nem perto de um iniciante em C #, mas não mexo no idioma há algum tempo, pois atualmente não tenho utilidade para ele no trabalho.

Os pontos salientes:

• Todas as classes ( Nil, Cons, Thunk) derivam de uma classe abstrata de base comum, List.

• A Thunkclasse usa o padrão Envelope-Letter . Isso emula essencialmente a self.__class__ = node.__class__atribuição na fonte Python, pois a thisreferência não pode ser modificada em C #.

• IsEmpty, Heade Tailsão propriedades.

• Todas as funções apropriadas são implementadas de forma recursiva e preguiçosa (exceto Print, que não pode ser preguiçosa) retornando thunks. Por exemplo, isto é Nil<T>.ZipWith:

  public override List<T> ZipWith(Func<T, T, T> func, List<T> other) {
      return Nil();
  }
  

  ... e é isso Cons<T>.ZipWith:

  public override List<T> ZipWith(Func<T, T, T> func, List<T> other) {
      return Thunk(() => {
          if (other.IsEmpty)
              return Nil();
  
          return Cons(func(Head, other.Head), Tail.ZipWith(func, other.Tail));
      });
  }
  

  Infelizmente, o C # não tem vários despachos, caso contrário, eu também poderia me livrar da ifdeclaração. Infelizmente, não há dados.

Agora, não estou muito feliz com minha implementação. Estou feliz até agora porque tudo isso é totalmente direto. Mas . Eu sinto que a definição de Fibé desnecessariamente complicada, pois preciso agrupar os argumentos em thunks para fazê-lo funcionar:

List<int> fib = null;
fib = List.Cons(0, List.Cons(1,
    List.ZipWith(
        (a, b) => a + b,
        List.Thunk(() => fib),
        List.Thunk(() => fib.Tail))));

(Aqui, List.Cons, List.Thunke List.ZipWithsão invólucros de conveniência.)

Gostaria de entender por que a seguinte definição muito mais fácil não está funcionando:

List<int> fib = List.Cons(0, List.Cons(1, List.Nil<int>()));
fib = fib.Concat(fib.ZipWith((a, b) => a + b, fib.Tail));

dada uma definição apropriada, é Concatclaro. Isso é essencialmente o que o código Python faz - mas não está funcionando (= jogando um ajuste).

/ EDIT: Joey apontou a falha óbvia nesta solução. No entanto, substituir a segunda linha por uma conversão também gera um erro (Mono segfaults; estou suspeitando de um estouro de pilha que o Mono não lida bem):

fib = List.Thunk(() => fib.Concat(fib.ZipWith((a, b) => a + b, fib.Tail)));

O código fonte completo pode ser encontrado como uma essência no GitHub .

Pico

para registro, esta solução usa uma conversão da força de atraso do esquema, conforme definido no srfi-45 . e cria listas preguiçosas em cima disso.

{ 
` scheme's srfi-45 begins here `

  _lazy_::"lazy";
  _eager_::"eager";

  lazy(exp())::[[_lazy_, exp]];
  eager(exp)::[[_eager_, exp]];
  delay(exp())::lazy(eager(exp()));

  force(promise)::
    { content:promise[1];
      if(content[1]~_eager_,
        content[2],
        if(content[1]~_lazy_,
          { promise_:content[2]();
            content:promise[1];
            if(content[1]~_lazy_, 
             { content_:promise_[1];
               content[1]:=content_[1];
               content[2]:=content_[2];
               promise_[1]:=content });
            force(promise) })) };

` scheme's srfi-45 ends here `

nil:delay([]);
is_nil(s):size(force(s))=0;
cons(a(),b()):delay([a(),b()]);
head(s):force(s)[1];
tail(s):force(s)[2];

zipWith(f,a,b):
  lazy(if(is_nil(a)|is_nil(b),
         nil,
         cons(f(head(a),head(b)), zipWith(f,tail(a),tail(b)))));

fibs:void;
fibs:=cons(0, cons(1, zipWith(+,fibs,tail(fibs))));

take(c,s):
  lazy(if((c=0)|(is_nil(s)),
         nil,
         cons(head(s),take(c-1,tail(s)))));

print(s):
  { comma(s):
      if(is_nil(s),
        void,
        { display(head(s));
          if(!(is_nil(tail(s))), display(","));
          comma(tail(s)) });
    display("[");
    comma(s);
    display("]");
    void };

print(take(40,fibs))

}

os olhares de saída como este: (mas dependendo de como tpico. é remendado ele pode ter citações mais duplas nele display. normalmente imprime strings com aspas ou seja, todas as aparências de [, ,, ]teria aspas em torno deles como "[".)

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]<void>

devido aos limites do tipo de dados inteiro no tpico, isso falha ao calcular o 45º (ou 46º deslocamento) número de Fibonacci.

note que o tpico 2.0pl11 está quebrado nisso begin(a,b)(que geralmente é escrito como {a;b}) e a iffunção não é recursiva da cauda. para não mencionar que demorei 5 anos para descobrir por que a begincauda não era recursiva. Também naquela época escrevi a tradução de srfi-45 no Pico. acabou sendo que beginestava aguardando o valor de bantes de retornar quando não precisou esperar. e quando cheguei, também consegui consertar if, pois tinha o mesmo problema. e houve esse outro erro que tornou o construtor de meta nível makeinoperante.

O Pico permite que uma função controle se seus argumentos são avaliados antes que a função seja chamada ou apenas empacotada como thunks. para esse código, posso reticências sobre as esquisitices de chamada por função .

Pico não tem inferência de tipo. Eu pensei sobre isso por um tempo, mas corri para um problema devido às peculiaridades da chamada por função . Eu vim com a declaração de que os tipos devem codificar a existência de nomes de variáveis ​​vinculados . mas eu estava pensando principalmente em como adaptar a inferência do tipo Hindley-Milner a um subconjunto do Pico sem mutação. a idéia principal era que o verificador de tipos retornasse vários esquemas possíveis se houver mais de uma ligação possível e a verificação de tipos seja bem-sucedida se houver pelo menos um esquema de tipos possível . um esquema possível é aquele em que nenhuma atribuição de tipo entra em conflito.