C'est un bon exercice pour devenir plus fluide dans ce langage de programmation que vous vouliez apprendre, mais que vous n'avez que légèrement modifié. Cela implique de travailler avec des objets, d'utiliser ou de simuler des fermetures et d'étirer le système de texte.

Votre tâche consiste à écrire du code pour gérer les listes paresseuses, puis à l'utiliser pour implémenter cet algorithme pour générer des nombres de Fibonacci:

Les exemples de code sont en Haskell

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

Résultat:

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

L'implémentation de votre liste paresseuse doit respecter ces directives:

• Un nœud de liste est l'une des trois choses:
  • Nil - Liste vide.
    []
  • Inconvénients - Un seul élément, associé à une liste des éléments restants:
    1 : [2,3,4,5]
    ( :est l'opérateur des inconvénients à Haskell)
  • Thunk - Un calcul différé qui produit un noeud List en cas de besoin.
• Il prend en charge les opérations suivantes:
  • nil - Construit une liste vide.
  • cons - Construit une cellule contre.
  • thunk - Construit un Thunk, étant donné une fonction qui ne prend aucun argument et renvoie un Nil ou un Cons.
  • force - Étant donné un nœud de liste:
    • Si c'est un néant ou un inconvénient, renvoyez-le simplement.
    • S'il s'agit d'un Thunk, appelez sa fonction pour obtenir un Nil ou un Cons. Remplacez le thunk par ce Nil ou Contre, et retournez-le.
      Remarque: le remplacement du thunk par sa valeur forcée est une partie importante de la définition de "paresseux" . Si cette étape est ignorée, l'algorithme de Fibonacci ci-dessus sera trop lent.
  • empty - Voir si un noeud List est Nil (après l'avoir forcé).
  • head (aka "car") - Obtenez le premier élément d'une liste (ou lancez un ajustement si c'est nul).
  • tail (aka "cdr") - Obtenez les éléments après la tête d'une liste (ou lancez un ajustement si c'est Nil).
  • zipWith - Étant donné une fonction binaire (par exemple (+)) et deux listes (éventuellement infinies), appliquez la fonction aux éléments correspondants des listes. Exemple:
    zipWith (+) [1,2,3] [1,1,10] == [2,3,13]
    
  • take - Étant donné un nombre N et une liste (éventuellement infinie), prenez les N premiers éléments de la liste.
  • print - Imprime tous les éléments d'une liste. Cela devrait fonctionner de manière incrémentielle lorsque vous disposez d'une liste longue ou infinie.

• fibss'utilise dans sa propre définition. La mise en place d'une récursivité paresseuse est un peu délicate; vous devrez faire quelque chose comme ceci:

  • Attribuer un thunk pour fibs. Laissez-le dans un état factice pour l'instant.
  • Définissez la fonction thunk, qui dépend d'une référence à fibs.
  • Mettez à jour le thunk avec sa fonction.

  Vous souhaiterez peut-être masquer cette plomberie en définissant une fonction fixqui appelle une fonction de retour de liste avec sa propre valeur de retour. Pensez à faire une petite sieste pour que cette idée puisse s'installer.

• Le polymorphisme (la capacité de travailler avec des listes de tout type d'élément) n'est pas requis, mais voyez si vous pouvez trouver un moyen de le faire qui soit idiomatique dans votre langue.

• Ne vous inquiétez pas de la gestion de la mémoire. Même les langages avec garbage collection ont tendance à transporter des objets que vous n'utiliserez plus jamais (par exemple sur la pile d'appels), alors ne soyez pas surpris si votre programme perd de la mémoire en parcourant une liste infinie.

N'hésitez pas à dévier légèrement de ces lignes directrices pour tenir compte des particularités de votre langue, ou pour explorer des approches alternatives aux listes paresseuses.

Règles:

• Choisissez une langue que vous ne connaissez pas bien. Je ne peux pas "exiger" cela, d'où la balise "honor-system". Cependant, les électeurs peuvent vérifier votre historique pour voir dans quelles langues vous avez posté.

• N'utilisez pas le support de liste paresseuse intégré de votre langue pour tout faire. Postez quelque chose de substantiel ou du moins intéressant.

  • Haskell est à peu près sorti. Autrement dit, à moins que vous ne fassiez quelque chose comme ceci:

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

    Remarque: l'évaluation non stricte de Haskell n'est pas interdite, mais l'implémentation de votre liste paresseuse ne doit pas en tirer directement la capacité. En fait, il serait intéressant de voir une solution efficace et purement fonctionnelle qui ne nécessite pas de paresse.

  • Python:

    • N'utilisez pas itertools.
    • Les générateurs vont bien, mais vous les utilisez, vous devrez trouver un moyen de mémoriser les valeurs forcées.

PostScript

J'ai déjà joué avec PostScript , mais je ne dirais pas que je le connais particulièrement bien (en fait, je suppose que vous pouvez compter le nombre de personnes dans le monde qui connaissent vraiment PostScript d'une seule main).

J'ai dévié de vos spécifications en ce que la fonction utilisée pour créer un thunk est autorisée à renvoyer un autre thunk; forcecontinuera à évaluer jusqu'à ce que le résultat soit un nilou un cons.

Les listes sont implémentées sous forme de dictionnaires:

<< /type /nil >>

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

<< /type /thunk
   /func evaluationFunction >>

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

Le code suit. Notez que nous remplaçons certains opérateurs intégrés (en particulier print; je n'ai pas vérifié s'il y en a plus); dans l'utilisation du monde réel, cela devrait être surveillé. Bien sûr, il n'y aura pas d'utilisation réelle, donc ça va.

Les commentaires avant les procédures doivent être lus comme

% before2 before1 before0  <| procedure |>  after1 after0

c'est-à-dire montrant le contenu attendu de la pile avant l'appel et le contenu résultant de la pile après l'appel. Les commentaires dans les procédures montrent le contenu de la pile après l'exécution de la ligne particulière.

% 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

Chargez ceci dans Ghostscript, en ignorant la page affichée - nous travaillons uniquement avec l'interpréteur. Voici l'algorithme 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>

Deux fonctions supplémentaires intéressantes:

% 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

Commencez à compter à 5, multipliez chaque élément de la liste résultante par 3 et affichez les dix premières valeurs:

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

Concernant le polymorphisme: Même si PostScript est fortement typé, il autorise des types arbitraires comme valeurs de dictionnaire, vous pouvez donc y ajouter tout ce que vous voulez:

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>

Notez que les erreurs de type, par exemple en essayant d'ajouter des chaînes aux nombres, ne se produiront qu'au moment de l'évaluation:

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

Je suis un débutant total en C, ce code est en fait la première vraie chose que j'ai codée en C. Il se compile sans aucun avertissement et fonctionne bien sur mon système.

Comment construire

Tout d'abord, récupérez l'archive tar de mon serveur . Il comprend un makefile, alors il suffit de l'exécuter makepour le créer, puis make runde l'exécuter. Le programme imprime ensuite une liste des 93 premiers nombres de fibonacci. (Après le numéro 94, un entier 64 bits non signé déborde)

Explication

Le noyau du programme est le fichier lazy-list.c. Dans le fichier d'en-tête correspondant, je définis une structure list, qui est notre liste paresseuse. Cela ressemble à ceci:

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

Le membre kindest une sorte de tag. Il marque, que l'on rechète les listes end ( NIL), une cellule déjà évaluée ( CONS) ou un thunk ( THUNK). Puis, suit une union. Il est

• soit une cellule déjà évaluée avec une valeur et une queue
• ou un thunk, comportant un pointeur de fonction et une structure, qui peut contenir des arguments à la fonction, si nécessaire.

Le contenu de l'union est affirmé par la balise. Si la balise est NIL, le contenu de l'union n'est pas défini.

En définissant les fonctions d'assistance mentionnées dans la spécification ci-dessus, on peut généralement extraire la définition des listes de son utilisation, par exemple. vous pouvez simplement appeler nil()pour obtenir une liste vide au lieu d'en créer une par vous-même.

Les trois fonctions les plus intéressantes sont zipWith, takeet fibonaccis. Mais je ne veux pas expliquer take, car il est très similaire à zipWith. Toutes les fonctions, qui fonctionnent paresseusement, ont trois composantes:

• Un wrapper, qui crée un thunk
• Un travailleur qui effectue les calculs pour une cellule
• Une structure qui garde les arguments

Dans le cas de zipWith, ce sont zipWith, __zipWithet __zipArgs. Je les montre juste ici sans autre explication, leur fonction devrait être assez claire:

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

L'autre fonction intéressante est fibonaccis(). Le problème est que nous devons passer un pointeur de la première et de la deuxième cellule au thunk de la troisième, mais pour créer ces cellules, nous avons également besoin d'un pointeur sur le thunk. Pour résoudre ce problème, j'ai rempli le pointeur sur le thunk avec une NULLpremière et l' ai changé en thunk, après sa création. Voici l'écoute:

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;

Améliorations possibles

• Ma solution n'utilise pas de polymorphisme. Bien que cela soit possible, mes compétences en C ne sont pas suffisantes pour savoir comment l'utiliser. Au lieu de cela, j'ai utilisé un type content_t, que l'on peut changer pour ce qui convient.
• On pourrait extraire le thunk de la définition de la liste et l'utiliser uniquement de manière abstraite, mais cela rendrait le code plus compliqué.
• On pourrait améliorer les parties de mon code qui ne sont pas bonnes C.

C ++

C'est la plus grande chose que j'aie jamais écrite en C ++. J'utilise normalement Objective-C.

C'est polymorphe mais ça ne libère jamais rien.

Ma mainfonction (et la addfonction à ZipWith) a fini par ressembler à ceci:

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

Cela donne

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

Les cours fonctionnent comme ceci:

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

Source complète: ici . C'est un gâchis, principalement parce que c'est dans un gros fichier.

Edit: changé le lien (l'ancien était mort).

Python

N'utilise pas de générateurs pour implémenter la liste, juste pour implémenter la __iter__méthode à utiliser avec 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)

La liste Fibonacci est créée comme suit:

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

Rubis

Mon premier programme Ruby. Nous représentons tous les nœuds sous forme de tableaux, où la longueur du tableau détermine le type:

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

Le code est alors assez simple, avec un hack pour réinitialiser la fonction thunk pour configurer le fib récursif.

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

Une langue relativement nouvelle, et je l'ai apprise en CTRL+Fing le 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()))
}

Le problème a été résolu en traitant les thunk-within-a-thunks. Cependant, il semble que le compilateur en ligne ne puisse pas prendre 40 éléments, peut-être à cause de la mémoire. Je le testerai plus tard sur mon 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

J'ai testé le code avec le compilateur en ligne , car je ne peux pas installer Go sur Windows facilement.

Cristal

Malgré le fait de suivre le référentiel GitHub, je n'ai jamais utilisé Crystal jusqu'à présent. Crystal est une variante Ruby de type statique avec une inférence de type complète. Même s'il existe déjà une réponse Ruby, le typage statique de Crystal m'a amené à utiliser le polymorphisme, plutôt qu'un tableau, pour représenter les nœuds. Parce que Crystal n'autorise pas la modification de self, j'ai créé une classe wrapper, nommée Node, qui envelopperait tout le reste et gérerait les thunks.

En plus des cours, j'ai créé les fonctions de constructeur lnil, conset thunk. Je n'ai jamais utilisé Ruby depuis plus d'un script de 20 lignes auparavant, donc le truc de bloc m'a beaucoup déstabilisé.

J'ai basé la fibfonction sur la réponse 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

J'ai un peu plié les règles car il n'y a pas encore de solution .NET ici - ou plus généralement une solution OOP à l'exception de celle en Python qui utilise l'héritage, mais elle est suffisamment différente de ma solution pour rendre les deux intéressantes (en particulier depuis Python permet de modifier l' selfinstance, ce qui rend l'implémentation du thunk simple).

C'est donc C # . Divulgation complète: je suis loin d'être un débutant en C # mais je n'ai pas touché la langue depuis un moment car je n'ai actuellement aucune utilité pour cela au travail.

Les points saillants:

• Toutes les classes ( Nil, Cons, Thunk) proviennent d'une classe de base abstraite commune, List.

• La Thunkclasse utilise le modèle Enveloppe-Lettre . Cela émule essentiellement l' self.__class__ = node.__class__affectation dans la source Python, car la thisréférence ne peut pas être modifiée en C #.

• IsEmpty, HeadEt Tailsont des propriétés.

• Toutes les fonctions appropriées sont implémentées de manière récursive et paresseuse (à l'exception de Print, qui ne peut pas être paresseux) en renvoyant les thunks. Par exemple, c'est Nil<T>.ZipWith:

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

  … Et c'est 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));
      });
  }
  

  Malheureusement, C # n'a pas de répartition multiple, sinon je pourrais également me débarrasser de la ifdéclaration. Hélas, pas de dés.

Maintenant, je ne suis pas vraiment satisfait de ma mise en œuvre. Je suis heureux jusqu'à présent, car tout ce qui précède est totalement simple. Mais . Je pense que la définition de Fibest inutilement compliquée car je dois envelopper les arguments dans les thunks pour le faire fonctionner:

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

(Ici, List.Cons, List.Thunket List.ZipWithenveloppent de commodité.)

Je voudrais comprendre pourquoi la définition beaucoup plus simple suivante ne fonctionne pas:

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

donné une définition appropriée de Concat, bien sûr. C'est essentiellement ce que fait le code Python - mais cela ne fonctionne pas (= lancer un ajustement).

/ EDIT: Joey a souligné le défaut évident de cette solution. Cependant, le remplacement de la deuxième ligne par un thunk génère également une erreur (Mono segfaults; je soupçonne un débordement de pile que Mono ne gère pas bien):

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

Le code source complet peut être trouvé en tant qu'essentiel sur GitHub .

Pico

pour mémoire, cette solution utilise une traduction de la force de retard du schéma telle que définie dans srfi-45 . et construit des listes paresseuses en plus de cela.

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

}

les regards de sortie comme ceci: (mais en fonction de la façon dont tpico. est patché , il pourrait avoir plus des guillemets doubles dans ce display. imprime normalement des chaînes avec des citations -à- dire toutes les apparences de [, ,, ]aurait des citations autour d' eux comme "[".)

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

en raison des limites du type de données entier dans tpico, cela échoue lors du calcul du 45e (ou 46e décalage) nombre de Fibonacci.

notez que tpico 2.0pl11 est cassé en cela begin(a,b)(qui est communément écrit comme {a;b}) et que la iffonction n'est pas récursive en queue. sans compter qu'il m'a fallu 5 ans pour comprendre pourquoi la beginqueue n'était pas récursive. à cette époque, j'ai également écrit la traduction de srfi-45 en Pico. il s'est avéré qu'il beginattendait la valeur de bavant de revenir alors qu'il n'avait pas besoin d'attendre. et une fois que j'ai obtenu cela, j'ai également pu le réparer ifcar il avait le même problème. et il y avait cette autre erreur qui a rendu le constructeur de niveau méta makeinopérant.

Pico permet à une fonction de contrôler si ses arguments sont évalués avant que la fonction soit appelée ou simplement empaquetée en tant que thunks. pour ce code, je peux faire des points de suspension sur les bizarreries de l' appel par fonction .

Pico n'a aucune inférence de type. J'ai réfléchi à cela pendant un certain temps mais j'ai rencontré un problème en raison des bizarreries de l' appel par fonction . je suis venu avec la déclaration que les types doivent coder l'existence de noms de variables liés . mais je pensais principalement à la façon d'adapter l'inférence de type Hindley-Milner à un sous-ensemble de Pico sans mutation. l'idée principale était que le vérificateur de type renvoie plusieurs schémas possibles s'il existe plusieurs liaisons possibles et que le contrôle de type réussit s'il existe au moins un schéma de type possible . un schéma possible est celui qu'aucun conflit d'attribution de type n'entre en conflit.