Mettez en place des listes paresseuses, de préférence dans une langue que vous ne connaissez pas bien [fermé]

21

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.
Joey Adams
la source
Quel devrait être le comportement lors de l'appel zipWithsur deux listes de longueurs différentes?
balpha
@balpha: J'ai choisi le comportement de Haskells: si l'une des listes est nulle, retournez zéro.
FUZxxl
@balpha: Dans Haskell, zipWith s'arrête lorsque l'une ou l'autre liste manque d'articles. Par conséquent, zipWith (+) [1,2,3,4,5] [0,0,0] == [1,2,3]. Cependant, cela n'a pas d'importance pour l'algorithme de Fibonacci ci-dessus, car les deux arguments de zipWith sont des listes infinies.
Joey Adams
Ce défi avait une surprise cachée: vous devez faire quelque chose de spécial pour l'implémenter fibscorrectement, car cela dépend de lui-même. J'ai mis à jour la question pour élaborer sur la récursivité paresseuse. FUZxxl l'a compris lui-même.
Joey Adams
Qu'entendez-vous par «travailler de manière incrémentielle» lorsque vous imprimez une grande liste?
Lowjacker

Réponses:

6

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--
balpha
la source
Incroyable. (Comment) forcemémorise- t- il les valeurs renvoyées?
Joey Adams
@JoeyAdams: En effet. Après avoir évalué un thunk, l' copyopérateur copie le contenu de la version évaluée dans l'original, en écrasant /typeet en définissant éventuellement d'autres valeurs. Après avoir évalué récursive jusqu'à ce que nous avons nilou cons, elle a aussi (via undef) Retire /funcet, le cas échéant, /data. La dernière étape n'est pas strictement nécessaire ( /funcet /dataserait simplement ignorée), mais laisser cette étape en dehors entraînerait une fuite de mémoire supplémentaire :)
balpha
6

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.
FUZxxl
la source
Belle soumission, surtout pour être un débutant en C. En ce qui concerne le polymorphisme, si vous êtes prêt à allouer tout votre contenu sur le tas, vous pouvez l'utiliser void*comme type de content_t.
Casey
@Casey: Merci beaucoup. J'ai pensé à l'utiliser void*aussi, mais je pensais que cela éluderait trop le système de caractères. N'est-ce pas possible en utilisant des modèles?
FUZxxl
C n'a pas de modèles, c'est-à-dire C ++, mais oui, vous pouvez utiliser des modèles C ++ pour le rendre générique.
Casey
Je ne sais pas comment les utiliser. Mais je suppose que c'est juste que C est un peu limité en termes de système de types. - Je n'ai même pas pu coder ce programme sans utiliser void*ni amis.
FUZxxl
1
« Le membre kindest en quelque sorte une étiquette. » Vous pouvez simplement l' appeler tag, comme c'est un joli accepté terme pour le concept (par exemple union taggés , Spineless Tagless G machine . D'autre part, « genre » a un sens différent dans un . contexte Haskell: le type d'un type Inta genre *, []a en quelque sorte * -> *, et (,)a en quelque sorte * -> * -> *.
Joey Adams
5

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

marinus
la source
3
Excellent travail, et merci d'avoir pris "throw a fit" littéralement :-) Je ne suis en aucun cas un expert en C ++, mais une façon plus C ++ - y d'implémenter Thunk pourrait être d'utiliser un objet fonction (aka "functor") (qui est, surcharger l' ()opérateur), et d'utiliser l'héritage pour éviter d'avoir à utiliser void*. Voir ici pour un exemple trivial de le faire.
Joey Adams
Le lien source complet est mort maintenant. Pourriez-vous le télécharger à nouveau? gist.github.com est un bon endroit pour le mettre.
Joey Adams
@JoeyAdams: terminé.
marinus
4

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()))
>>> 
Lowjacker
la source
1
C'est beau. Ma ligne préférée est self.__class__ = node.__class__. Notez que cela frappe une exception NotImplemented lorsqu'il atteint 2971215073 (long), ce qui est apparemment un argument non valide pour int .__ add__. Pour prendre en charge les grands nombres entiers, faitesfib.append(fib.zip_with(lambda a,b: a+b, fib.tail()))
Joey Adams
1
Pourquoi ne pouvez-vous pas ajouter à vide ou thunk?
PyRulez
4

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))
Keith Randall
la source
Vous pouvez utiliser à la [...]place de Array[...].
Lowjacker
3

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.

Ming-Tang
la source
C'est assez joli et simple. Cependant, au lieu de 3 bools, vous pouvez utiliser une seule balise dont les valeurs possibles sont des constantes générées par le iotagénérateur de constantes. Voir un exemple dans la spécification du langage de programmation Go et une réponse sur StackOverflow .
Joey Adams
Votre Fibsfonction ne fonctionne pas car Go utilise une évaluation stricte et se Fibsreproduit sur elle-même sans condition de terminaison. Fibs0/ Fibs1utilise une approche de générateur simple plutôt que l'algorithme décrit dans mon article, donc il ne répond pas aux "exigences". J'ai mis à jour mon message pour élaborer sur la récursivité paresseuse, qui est nécessaire pour implémenter fibs = 0 : 1 : zipWith (+) fibs (tail fibs) .
Joey Adams
Cons(0, Cons(1, ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs))))), ça sort de la mémoire
Ming-Tang
J'ai essayé Cons(0, Cons(1, Thunk(func() List { return ZipWith(Plus, Thunk(Fibs), Thunk(func() List { return Tail(Fibs()) })) })))et j'obtiens une erreur d'adresse mémoire invalide
Ming-Tang
1
Puisque vous apprenez encore Go: vous pouvez créer du code beaucoup plus élégant que cela en utilisant des interfaces pour les listes et des types distincts pour Thunks, etc.
cthom06
3

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
kirbyfan64sos
la source
2

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 .

Konrad Rudolph
la source
"Malheureusement, C # n'a pas de répartition multiple" - vous pouvez obtenir l'effet en utilisant des événements, bien que ce soit plutôt hacky.
Peter Taylor
L'ironie de l'évaluation paresseuse est qu'elle nécessite la mise en œuvre de l'état. fib.ZipWithet fib.Tailutiliser l'ancien fib, qui reste [0,1]et ne change pas. Ainsi, vous obtenez [0,1,1](je pense), et votre Takefonction ne vous permet pas de prendre de null (la prise de Haskell le fait, cependant). Essayez de placer la valeur r de la deuxième ligne dans un thunk, afin qu'elle se réfère à la nouvelle fibplutôt qu'à l'ancienne.
Joey Adams
@Peter Oui; vous pouvez également utiliser le modèle Visitor pour implémenter la répartition multiple, mais je voulais que la solution reste simple.
Konrad Rudolph
@Joey Duh. C'est aveuglément évident maintenant. Cependant, la solution thunk ne fonctionne toujours pas (voir la réponse mise à jour) mais je suis trop occupé maintenant pour enquêter.
Konrad Rudolph
2

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.

Dan D.
la source