Comment les langages purement fonctionnels gèrent-ils les algorithmes basés sur l'indice?

Ce n'est pas une réponse Haskell, mais vous avez marqué la question Lisp alors voici une réponse dans Racket: c'est à la fois entièrement fonctionnel et montre que vous n'avez pas besoin d'indices pour ce problème. Ce que fait cette fonction, c'est prendre un flux de nombres et renvoyer le flux de préfixe pour lui. Tout cela est fait paresseusement.

(stream->list (stream-take (prefix-stream (in-naturals)) 10))
'(0 1 3 6 10 15 21 28 36 45)
> (stream->list (stream-take (stream-tail (prefix-stream (in-naturals)) 1000) 10))
'(500500 501501 502503 503506 504510 505515 506521 507528 508536 509545)

Alors maintenant

> (prefix-stream (in-naturals))
#<stream>

mais bien sûr, vous pouvez également le faire:

> (stream->list (prefix-stream (in-range 1 10)))
'(1 3 6 10 15 21 28 36 45)

Ce n'est évidemment pas un flux que vous pouvez convertir en liste, mais vous pouvez en regarder des parties:

(define (prefix-stream s)
  (let ps-loop ([st s]
                [p 0])
    (if (stream-empty? st)
        empty-stream
        (let ([np (+ p (stream-first st))])
          (stream-cons 
              np 
              (ps-loop 
                  (stream-rest st)
                  np))))))

(Remarque que en nature considère les naturels de commencer à 0, comme c'est bien et propre.)

Dans Clojure, cela pourrait être écrit comme:

(defn prefix-list [nums]
  (loop [i 1
         prefix nums]
    (if (= i (count nums))
      prefix
      (recur (inc i) (assoc prefix i (+ (get prefix i) (get prefix (dec i))))))))

(préfixe-list [1 2 3 4 5 6 7 8 9]) renvoie [ 1 3 6 10 15 21 28 36 45]

Dans Clojure, les données sont généralement immuables (elles ne peuvent pas être modifiées). La fonction association dans ce cas prend un vecteur et renvoie un nouveau vecteur comme l'original, mais avec le i

th

élément modifié. Cela peut sembler inefficace, mais les structures de données sous-jacentes permettent de faire la mise à jour en un temps presque constant ( o (log (n))).

Comme d'autres l'ont souligné, ce problème particulier pourrait être codé sans utiliser de vecteurs indexés, mais je m'efforce de fournir une solution fidèle à votre code Java d'origine dans l'utilisation d'un tableau indexé.

Je sais que vous avez posé des questions sur les langages fonctionnels, mais je voulais juste que le carillon ne soit pas invité pour mentionner que Python, étant une langue multi-paradigme, a également cela comme le joli ordre supérieur itertools.accumulate Fonction.

accumuler prend une collection et renvoie un itérateur de ses sommes partielles, ou toute fonction binaire personnalisée. Le code Python fonctionnel équivalent à votre exemple ne serait que:

from itertools import accumulate
print(list(accumulate(range(1, 10))))

En général, le python itertools et functools / a > Les modules de bibliothèque standard offrent d'excellents outils pour la programmation fonctionnelle.

Cette fonctionnalité est également appelée "somme cumulative", et une autre méthode Python consiste à utiliser numpy (qui, étant écrit en c, est ultra rapide):

[1, 3, 6, 10, 15, 21, 28, 36, 45]

sortie:

nums = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9]) # or np.arange(1, 10) or np.arange(9)+1
print(nums.cumsum())

p>

D'autres ont souligné que votre exemple particulier peut être bien géré avec des fonctions comme scanl exécution". Nous pouvons décomposer le problème en trois préoccupations:

L'indexation dans une structure de données est prise en charge partout où le concept d'indexation est logique. Par exemple, list et vector prennent en charge l'indexation. Comme d'autres l'ont souligné, vector a de meilleures performances si votre index est aléatoire, mais c'est étonnamment rare.

Les boucles impératives peuvent être remplacées directement par des fonctions récursives (voir wikpedia ) Bien qu'il existe tellement de «fonctions d'ordre supérieur» (fonctions qui prennent des fonctions comme des arguments) implémentées dans les bibliothèques prélude et standard dont vous aurez besoin rarement de récursivité explicite. Scanl en est un exemple. Il vous permet d'éviter un appel récursif explicite en l'élevant à une fonction pré-écrite. Cette fonction, cependant, est définie de manière récursive . Le compilateur peut optimiser cette récursivité dans une boucle lorsqu'elle génère du code machine.

Enfin, vous pourriez avoir un tableau de nombres et vous voulez vraiment, vraiment muter les valeurs dans le tableau sur une série d'étapes. Tout le monde dans ce fil, y compris moi, s'efforcerait de vous en parler et de vous faire penser d'une manière plus "fonctionnelle". Mais si nous échouons, vous pouvez utiliser le État thread monad . Cela vous donne un moyen de muter vos structures de données localement (effrayantes) dans une fonction tout en interagissant avec les choses en dehors de la fonction uniquement avec des structures de données immuables (pas effrayantes) et garantit donc que la fonction est référentiellement transparent .

Il existe des fonctions intégrées dans Elixir qui sont similaires aux Haskell: enum.scan / 2 et enum.scan / 3 :

defmodule Foo do
  def bar(nums, acc \\ [])

  # We've reached the end of input: return the accumulator (reversed)
  def bar([], acc), do: Enum.reverse(acc)

  # The very first call is special because we do not have a previous value
  def bar([x | tail], []) do
    bar(tail, [x])
  end

  # All other calls land here
  def bar([x | tail], [prev | _] = acc) do
    bar(tail, [x + prev | acc])
  end
end


nums =   [1, 2, 3, 4,  5,  6,  7,  8,  9]
prefix = Foo.bar(nums)
IO.inspect(prefix)

# Yields the same result:
# [1, 3, 6, 10, 15, 21, 28, 36, 45]