En essayant d'apprendre Haskell, je suis tombé sur ce modèle simple à quelques reprises récemment:
Disons que j'ai une liste de quelque chose et je veux mettre à jour tous les éléments d'une sous-liste, par exemple de l'index i à j.
Toutes les solutions que je peux trouver me semblent vraiment piratées et mauvaises, comme cet exemple:
import qualified Data.Sequence as S increment :: Int -> Int -> S.Seq Int -> S.Seq Int increment i j sq | i <= j = increment (i + 1) to (S.adjust (+1) i sq) | otherwise = sq
Je suppose que je ferais encore pire avec un liste.
Quelqu'un connaît-il un moyen simple de le faire? J'ai essayé de chercher, et aussi de regarder les bibliothèques standard (Data.Array, Data.Vector, etc.) mais il y a quelque chose dans la façon dont il est écrit qui fait un peu saigner mes yeux et je veux des conseils humains
p>
3 Réponses :
Nous devons y penser de manière plus fonctionnelle. Si nous regardons:
inc1 (inc2 (inc3 seq0))
Il faut un index pour ajuster, l'ajustement à appliquer, et une séquence, et retourne une nouvelle séquence. Pour ajuster un tas d'éléments, nous ajustons le premier, puis ajustons le second au résultat du premier ajustement, et ainsi de suite. Tout d'abord, nous pouvons faire une liste de tous les ajustements que nous voulons faire:
adjustments = [inc1, inc2, inc3]
(attention: ceci est une liste de fonctions). Ensuite, je veux appliquer l'un après l'autre à une séquence de départ. Donc, si la liste finit par être
adjustments :: [S.Seq Int -> S.Seq Int] adjustments = [ S.adjust i (+1) | i <- [lower..upper] ]
Nous voulons obtenir
S.adjust :: Int -> (a -> a) -> S.Seq a -> S.Seq a
où seq0
est la séquence entrante initiale. Cette approche a-t-elle un sens? est-ce suffisant pour vous lancer?
Une approche plus efficace consiste à diviser la séquence aux deux extrémités, à utiliser fmap
sur la partie centrale, puis à joindre les parties ensemble.
increment :: Int -> Int -> S.Seq Int -> S.Seq Int increment i j sq = sq0 S.>< fmap (+ 1) sq1 S.>< sq2 where (sq01, sq2) = S.splitAt (j + 1) sq (sq0, sq1) = S.splitAt i sq01
J'ai essayé de chercher, et aussi de regarder les bibliothèques standard (Data.Array, Data.Vector, etc.) mais il y a quelque chose dans la façon dont il est écrit qui fait un peu saigner mes yeux et je veux des conseils humains >
Oui, il est simple d'utiliser
Data.Array
pour doubler le problème impliquant l'index. Pour un tableau immuable, vous pouvez utiliser la fonctionaccum
pour mettre à jour les éléments du tableau avec une liste de paires(index, valeur)
pour spécifier l'index et la valeur.Par exemple, supposons que nous devions ajouter 1 aux éléments du tableau
[1,2,3,4,5,6,7,8,9,10]
à partir de l'index 2 à 4.Fristement, construis un tableau à partir de la liste
[1,2,3,4,5,6,7,8,9,10]
:accum (flip const) testArray (zip [2..4] (repeat 0))et appliquez la fonction
accum
au tableau:[1,2,4,5,6,6,7,8,9,10]Notez que
(zip [i ..j] (répéter 1))
construit une liste de paires, sii = 2 et j = 4
donne:elems $ increment' 2 4 testArrayla première valeur de la paire est l'index du tableau et la seconde est le deuxième argument de
(+)
,accum
récupère la valeur de l'index spécifique et applique(+ 1)
à la valeur, c'est exactement ce que nous voulons. Pour le tester:[(2, 1), (3, 1), (4, 1)]donne
increment' i j ary = accum (+) ary (zip [i..j] (repeat 1))Sinon, si vous voulez simplement remplacer l'ancienne valeur de array par new valeur et peu importe quelle est l'ancienne valeur. La fonction
accum
peut également être appliquée dans cette situation. Par exemple, supposons de remplacer les éléments d'index 2 à 4 par0
:testArray = let xs = [1..10] in listArray (0, length xs-1) xs
Vous voulez dire décrémenter tous les éléments entre l'index
i
etj
? "Décrémenter tous les nombres entiers 0 <= i <= jCela peut paraître évident pour vous, mais qu'est-ce que
S
? Veuillez ajouter la déclaration d'importation appropriée.@WillemVanOnsem cela devrait devenir clair à partir de la définition de la fonction
@Amoz: à proprement parler si vous dites " Disons que j'ai une liste d'entiers de longueur N et que je veux incrémenter tous les entiers 0 <= i <= j", alors cela signifie que vous veulent décrémenter des éléments dans une liste pour laquelle les entiers " 0 <= i <= j " sont maintenus, mais 0 <= i <= j sont non entiers, c'est un booléen (enfin sauf si on étend l'opérateur "<=", etc.). donc la définition actuelle n'a pas beaucoup de sens.
@WillemVanOnsem Merci, je comprends votre point. J'ai pensé que le mot «index» dans le titre pouvait suffire. J'ai édité mon message! merci pour vos commentaires