Jest to fajne ćwiczenie, dzięki któremu można płynniej posługiwać się tym językiem programowania, którego zamierzałeś się uczyć, ale majstrowałeś tylko lekko. Obejmuje to pracę z obiektami, używanie lub symulowanie zamknięć i rozciąganie układu czcionek.

Twoim zadaniem jest napisanie kodu do zarządzania listami leniwymi, a następnie użycie go do zaimplementowania tego algorytmu do generowania liczb Fibonacciego:

Próbki kodu znajdują się w Haskell

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

Wynik:

[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]

Implementacja listy leniwej powinna spełniać następujące wytyczne:

• Węzeł listy jest jedną z trzech rzeczy:
  • Zero - pusta lista.
    []
  • Wady - Pojedynczy element, w połączeniu z listą pozostałych elementów:
    1 : [2,3,4,5]
    ( :jest operatorem wad w Haskell)
  • Thunk - odroczone obliczenia, które w razie potrzeby tworzą węzeł List.
• Obsługuje następujące operacje:
  • zero - Zbuduj pustą listę.
  • Minusy - Zbuduj komórkę przeciw.
  • thunk - Zbuduj Thunk, biorąc pod uwagę funkcję, która nie przyjmuje argumentów i zwraca zero lub minus.
  • force - Biorąc pod uwagę węzeł listy:
    • Jeśli jest to zero lub minus, po prostu go zwróć.
    • Jeśli jest to Thunk, wywołaj jego funkcję, aby uzyskać zero lub minusy. Wymień thunk na zero lub minusy i zwróć go.
      Uwaga: Zastąpienie thunk jego wymuszoną wartością jest ważną częścią definicji „leniwy” . Jeśli ten krok zostanie pominięty, powyższy algorytm Fibonacciego będzie zbyt wolny.
  • puste - Sprawdź, czy węzeł listy ma wartość zero (po wymuszeniu).
  • head (aka „car”) - Zdobądź pierwszą pozycję na liście (lub rzuć dopasowanie, jeśli to zero).
  • tail (aka „cdr”) - Pobierz elementy za nagłówkiem listy (lub rzuć pas, jeśli jest zero).
  • zipWith - Biorąc pod uwagę funkcję binarną (np. (+)) i dwie (być może nieskończone) listy, zastosuj funkcję do odpowiednich pozycji list. Przykład:
    zipWith (+) [1,2,3] [1,1,10] == [2,3,13]
    
  • take - Biorąc pod uwagę liczbę N i listę (być może nieskończoną), weź pierwsze N ​​elementów listy.
  • print - Wydrukuj wszystkie elementy z listy. Powinno to działać przyrostowo, jeśli podano długą lub nieskończoną listę.

• fibsużywa się w swojej własnej definicji. Konfigurowanie leniwej rekurencji jest nieco trudne; musisz zrobić coś takiego:

  • Przydziel thunk za fibs. Na razie pozostaw to w stanie manekina.
  • Zdefiniuj funkcję thunk, która zależy od odwołania do fibs.
  • Zaktualizuj thunk z jego funkcją.

  Możesz ukryć tę hydraulikę, definiując funkcję, fixktóra wywołuje funkcję zwracającą listę z własną wartością zwracaną. Rozważ krótką drzemkę, aby ten pomysł mógł się wprowadzić.

• Polimorfizm (zdolność do pracy z listami dowolnego rodzaju przedmiotów) nie jest wymagany, ale sprawdź, czy możesz znaleźć sposób, aby to zrobić, idiomatyczne w twoim języku.

• Nie martw się o zarządzanie pamięcią. Nawet języki z odśmiecaniem mają tendencję do przenoszenia obiektów, których już nigdy nie użyjesz (np. Na stosie wywołań), więc nie zdziw się, jeśli twój program wycieknie pamięć podczas przeglądania nieskończonej listy.

Zachęcamy do nieznacznego odstępstwa od tych wytycznych, aby uwzględnić szczegóły dotyczące Twojego języka, lub do poszukiwania alternatywnych podejść do leniwych list.

Zasady:

• Wybierz język, którego nie znasz dobrze. Nie mogę tego „wymagać”, stąd tag „honor-system”. Głosujący mogą jednak sprawdzić Twoją historię, aby zobaczyć, w jakich językach piszesz.

• Nie używaj wbudowanej obsługi leniwych list w swoim języku do robienia wszystkiego. Zamieść coś znaczącego lub co najmniej interesującego.

  • Haskell jest prawie nieobecny. To znaczy, chyba że zrobisz coś takiego:

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

    Uwaga: nie ścisła ocena Haskell nie jest niedostępna, ale implementacja leniwej listy nie powinna bezpośrednio czerpać z niej możliwości. W rzeczywistości interesujące byłoby stworzenie wydajnego, czysto funkcjonalnego rozwiązania, które nie wymaga lenistwa.

  • Pyton:

    • Nie używaj narzędzi itertools.
    • Generatory są w porządku, ale korzystasz z nich, musisz znaleźć sposób na zapamiętanie wartości wymuszonych.

Postscriptum

Mam grał z PostScript przed , ale nie powiedziałbym, wiem to szczególnie dobrze (w rzeczywistości, wydaje mi się, że można policzyć liczbę ludzi na świecie, który naprawdę zna PostScript jedną ręką).

Odszedłem od twojej specyfikacji, ponieważ funkcja użyta do utworzenia thunk może zwrócić kolejną thunk; forcebędzie kontynuować ocenę, aż wynik będzie a nillub a cons.

Listy są implementowane jako słowniki:

<< /type /nil >>

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

<< /type /thunk
   /func evaluationFunction >>

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

Kod następuje. Zauważ, że nadpisujemy niektóre wbudowane operatory (w szczególności print; nie sprawdziłem, czy jest więcej); w prawdziwym świecie trzeba to uważać. Oczywiście nie będzie żadnego zastosowania w świecie rzeczywistym, więc nie ma sprawy.

Komentarze przed procedurami należy rozumieć jako

% before2 before1 before0  <| procedure |>  after1 after0

tzn. wyświetlenie oczekiwanej zawartości stosu przed wywołaniem i wynikowej zawartości stosu po wywołaniu. Komentarze w ramach procedur pokazują zawartość stosu po wykonaniu określonego wiersza.

% 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

Załaduj to do Ghostscript, ignorując wyświetlaną stronę - pracujemy tylko z tłumaczem. Oto algorytm Fibonacciego:

[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>

Dwie dodatkowe ciekawe funkcje:

% 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

Rozpocznij liczenie od 5, pomnóż każdy element wynikowej listy przez 3 i wyświetl pierwsze dziesięć wartości:

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

Odnośnie polimorfizmu: Pomimo tego, że PostScript jest silnie pisany, pozwala na dowolne typy jako wartości słownikowe, dzięki czemu możesz wrzucić dowolne:

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>

Pamiętaj, że błędy literowe, np. Podczas próby dodania ciągów do liczb, będą występować tylko w czasie oceny:

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--

do

Jestem całkowicie początkującym w C, ten kod jest właściwie pierwszą prawdziwą rzeczą, którą napisałem w C. Kompiluje się bez ostrzeżeń i działa dobrze w moim systemie.

Jak zbudować

Najpierw pobierz tarball z mojego serwera . Zawiera plik makefile, więc po prostu uruchom, makeaby go zbudować, a następnie make runuruchomić. Następnie program wypisuje listę pierwszych 93 liczb Fibonacciego. (Po numerze 94 przepełnia się 64-bitowa liczba całkowita bez znaku)

Wyjaśnienie

Rdzeniem programów jest plik lazy-list.c. W odpowiednim pliku nagłówkowym definiuję struct list, czyli naszą leniwą listę. To wygląda tak:

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;
};

Członek kindjest rodzajem tagu. Oznacza to, czy odwołaliśmy listę end ( NIL), komórkę, która jest już oceniana ( CONS), czy thunk ( THUNK). Potem następuje związek. To jest

• albo już oceniona komórka z wartością i ogonem
• lub thunk, zawierający wskaźnik funkcji i strukturę, które mogą zawierać argumenty funkcji, jeśli to konieczne.

Zawartość związku jest potwierdzana przez tag. Jeśli tag jest NIL, treść związku jest niezdefiniowana.

Definiując funkcje pomocnicze wspomniane w powyższej specyfikacji, zwykle można wyodrębnić definicję listy z jej użycia, np. możesz po prostu zadzwonić, nil()aby uzyskać pustą listę zamiast tworzyć ją samodzielnie.

Trzy najciekawsze funkcje to zipWith: takei fibonaccis. Ale nie chcę wyjaśniać take, ponieważ jest bardzo podobny do zipWith. Wszystkie działające leniwie funkcje mają trzy elementy:

• Owijka, która tworzy zgrzyt
• Pracownik, który wykonuje obliczenia dla jednej komórki
• Struktura, która przechowuje argumenty

W przypadku zipWith, są zipWith, __zipWithi __zipArgs. Pokazuję je tutaj bez dalszych wyjaśnień, funkcja powinna być całkiem jasna:

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);
}

Inną interesującą funkcją jest fibonaccis(). Problem polega na tym, że musimy przekazać wskaźnik pierwszej i drugiej komórki do nasadki trzeciej, ale aby utworzyć te komórki, potrzebujemy również wskaźnika do nasadki. Aby rozwiązać ten problem, NULLnajpierw wypełniłem wskaźnik do klocka i po utworzeniu zmieniłem go w klocek. Oto słuchanie:

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;

Możliwe ulepszenia

• Moje rozwiązanie nie wykorzystuje polimorfizmu. Chociaż możliwe, moje umiejętności C nie są wystarczające, aby wiedzieć, jak go używać. Zamiast tego użyłem typu content_t, który można zmienić na dowolny pasujący.
• Można wyodrębnić thunk z definicji listy i użyć go tylko abstrakcyjnie, ale zrobienie tego uczyniłoby kod bardziej skomplikowanym.
• Można poprawić części mojego kodu, które nie są dobre C.

C ++

To największa rzecz, jaką kiedykolwiek napisałem w C ++. Zwykle używam Objective-C.

Jest polimorficzny, ale nigdy niczego nie uwalnia.

Moja mainfunkcja (i addfunkcja do ZipWith) wyglądała tak:

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;
}

To daje

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

Klasy działają w następujący sposób:

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()

Pełne źródło: tutaj . To bałagan, głównie dlatego, że jest w jednym dużym pliku.

Edycja: zmieniono link (stary nie żył).

Pyton

Nie używa generatorów do implementacji listy, tylko do implementacji __iter__metody do użycia z 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)

Lista Fibonacciego jest tworzona w następujący sposób:

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

Rubin

Mój pierwszy program Ruby. Wszystkie węzły reprezentujemy jako tablice, których długość określa typ tablicy:

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

Kod jest więc dość prosty, z hackem, aby zresetować funkcję thunk, aby skonfigurować rekurencyjne fib.

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

Względnie nowy język i nauczyłem się go, CTRL+Fwprowadzając 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()))
}

Problem został rozwiązany, radząc sobie z thunk-in-a-thunks. Wydaje się jednak, że kompilator online nie może przyjąć 40 elementów, być może z powodu pamięci. Później przetestuję to na moim systemie Linux.

[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

Przetestowałem kod za pomocą kompilatora online , ponieważ nie mogę łatwo zainstalować Go w systemie Windows.

Kryształ

Pomimo przestrzegania repozytorium GitHub, do tej pory nigdy nie korzystałem z Crystal. Crystal to statycznie wpisany wariant Ruby z pełnym wnioskowaniem typu. Mimo że istnieje już odpowiedź Ruby, statyczne pisanie Crystal doprowadziło mnie do użycia polimorfizmu zamiast tablicy do reprezentowania węzłów. Ponieważ Crystal nie zezwala na modyfikację self, stworzyłem klasę otoki o nazwie Node, która owinąłaby wszystko inne i zarządzałaby zespołami.

Wraz z klas I stworzył funkcji konstruktora lnil, consoraz thunk. Nigdy wcześniej nie używałem Ruby do więcej niż 20-liniowego skryptu, więc blokowanie mnie trochę odrzuciło.

Oparłem tę fibfunkcję na odpowiedzi 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

Wygiąłem trochę reguły, ponieważ nie ma tu jeszcze rozwiązania .NET - lub bardziej ogólnie rozwiązania OOP, z wyjątkiem rozwiązania w Pythonie, które korzysta z dziedziczenia, ale jest wystarczająco różne od mojego rozwiązania, aby uczynić oba interesującymi (w szczególności od Pythona pozwala modyfikować selfinstancję, dzięki czemu implementacja Thunk jest prosta).

To jest C # . Pełne ujawnienie: nie jestem nigdzie w pobliżu początkującego w C #, ale od jakiegoś czasu nie dotknąłem tego języka, ponieważ w tej chwili nie mam z niego pożytku w pracy.

Istotne punkty:

• Wszystkie klasy ( Nil, Cons, Thunk) wywodzą się od wspólnego abstrakcyjnej klasy bazowej List.

• ThunkKlasa używa Koperta-literowy wzór. Zasadniczo emuluje to self.__class__ = node.__class__przypisanie w źródle Pythona, ponieważ thisodwołania nie można modyfikować w języku C #.

• IsEmpty, HeadI Tailmają właściwości.

• Wszystkie odpowiednie funkcje są zaimplementowane rekurencyjnie i leniwie (z wyjątkiem tych Print, które nie mogą być leniwe) przez zwracanie części. Na przykład jest to Nil<T>.ZipWith:

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

  … A to jest 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));
      });
  }
  

  Niestety, C # nie ma wielu wysyłek, w przeciwnym razie mógłbym również pozbyć się ifinstrukcji. Niestety, nie ma kości.

Teraz nie jestem naprawdę zadowolony z mojej implementacji. Do tej pory jestem szczęśliwy, ponieważ wszystkie powyższe są całkowicie proste. Ale … Wydaje mi się, że definicja Fibjest niepotrzebnie skomplikowana, ponieważ muszę zawrzeć argumenty w gromady, aby działało:

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

(Tutaj List.Cons, List.Thunki List.ZipWithsą obwolut wygody.)

Chciałbym zrozumieć, dlaczego następująca znacznie łatwiejsza definicja nie działa:

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

Concatoczywiście z odpowiednią definicją . Jest to w zasadzie to, co robi kod Pythona - ale nie działa (= rzucanie pasowaniem).

/ EDIT: Joey zwrócił uwagę na oczywistą wadę tego rozwiązania. Jednak zamiana drugiej linii na thunk również powoduje błąd (Mono segfaults; Podejrzewam przepełnienie stosu, którego Mono nie radzi sobie dobrze):

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

Pełny kod źródłowy można znaleźć w GitHub jako gist .

Pico

dla przypomnienia , w tym rozwiązaniu zastosowano translację siły opóźnienia schematu zdefiniowanej w srfi-45 . i na tym buduje leniwe listy.

{ 
` 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))

}

wygląd wyjściowe tak: (ale w zależności od sposobu tpico, jest połatany może mieć więcej cudzysłowów w nim display. normalnie drukuje łańcuchy z cytatami czyli wszystkie występy [, ,, ]musiałby cudzysłowy wokół nich niczym "[").

[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>

ze względu na ograniczenia typu danych liczb całkowitych w tpico nie udaje się to przy obliczeniu 45. (lub 46. przesunięcia) liczby Fibonacciego.

Zauważ, że tpico 2.0pl11 jest zepsuty w tym begin(a,b)(co zwykle jest pisane jako {a;b}), a iffunkcja nie jest rekurencyjna. nie wspominając o tym, że zajęło mi 5 lat, aby dowiedzieć się, dlaczego beginnie był rekurencyjny. również w tym czasie napisałem tłumaczenie srfi-45 w Pico. okazało się, że beginczekało na wartość bprzed powrotem, gdy nie musiało czekać. a kiedy już to dostałem, byłem w stanie to naprawić, ifponieważ miał ten sam problem. był też inny błąd, który spowodował, że konstruktor meta-poziomu makenie działał.

Pico pozwala funkcji kontrolować, czy jej argumenty są sprawdzane, zanim funkcja zostanie wywołana lub po prostu spakowana jako thunks. w przypadku tego kodu mogę wymyślić wielokropek wywołania według funkcji .

Pico nie ma wnioskowania o typie. zastanawiałem się przez chwilę, ale natknąłem się na problem z powodu osobliwości wywołania według funkcji . wpadłem na stwierdzenie, że typy muszą kodować istnienie powiązanych nazw zmiennych . ale myślałem głównie o tym, jak dostosować wnioskowanie typu Hindleya-Milnera do podzbioru Pico bez mutacji. główną ideą było to, że moduł sprawdzania typu zwraca wiele możliwych schematów, jeśli istnieje więcej niż jedno możliwe powiązanie, a sprawdzanie typu kończy się powodzeniem, jeśli istnieje co najmniej jeden możliwy schemat typów . możliwym schematem jest taki, który nie powoduje konfliktu przypisania typu.