et RPL : Scan

En APL il existe l’opérateur  \ (appelé scan ou balayage ou réduction partielle) qui fait penser à l’opérateur / de réduction. Voici la différence :

f/ 1 2 3 … = 1 f 2 f 3 …
f\ 1 2 3 … = (f/1) (f/1 2) (f/1 2 3) …

Le n-ieme résultat est égal à la réduction des n premiers éléments. L’exemple de base est la somme cumulée des éléments d’un vecteur :

+\ 2 3 4 8 10
2 5 9 17 27

On peut imaginer une version en RPL utilisant SEQ pour créer ces suites ou rester avec notre trio DOLIST, DOSUBS et STREAM. En effet, si on reprend la réduction :

1: { 2 3 4 8 10 }
« + »
PRG LIST PROC STREAM
1: 27

Mais si l’on ajoute OVER pour dupliquer à chaque fois le résultat précédent :

1: { 2 3 4 8 10 }
« OVER + »
PRG LIST PROC STREAM
5: 2
4: 5
3: 9
2: 17
1: 27

On obtient les bonnes valeurs mais elles seront sur la pile. Pour comprendre le principe, tapez sur votre machine :
2 ENTER 3 OVER + 4 OVER + 8 OVER + 10 OVER +

Reste à la transformer en liste { 2 5 9 17 27}. On peut  imaginer cette version pour le cas d’une somme cumulée :

« → v
 « v « OVER + » STREAM v SIZE →LIST »
»
'SCUM STO

1: { 2 5 3 4}
VAR SCUM
1: {2 7 10 14}

Ou, de façon plus générale, définir SCA. (Scan), appelé PRED dans le document d’origine de Norman Brenner) :

« → v f
 « v « OVER f EVAL » STREAM v SIZE →LIST »
»
'SCA. STO

Exemples :

1: {1 2 3 4}
2: « + »
VAR SCA.
1: {1 3 6 10}

1: {2 5 4 1 8 3 3}
2: « MAX »
VAR SCA.
1: {2 5 5 5 8 8 8}  # Maximum progressif

En APL :

⌈\ 2 5 4 1 8 3 3
2 5 5 5 8 8 8

En particulier, lorsque les vecteurs sont binaires, cela permet d’avoir des résultats intéressants :

∧\ 1 1 1 0 1 0 0 1
   1 1 1 0 0 0 0 0    ⍝ = 0 à partir du 1er "0"
∨\ 0 0 0 0 1 0 0 1
   0 0 0 0 1 1 1 1    ⍝ = 1 à partir du 1er "1"
<\ 0 0 1 0 1 1 0 0 1
   0 0 1 0 0 0 0 0 0  ⍝ Position du 1er "1"

En RPL :

2: {1 1 1 0 1 0 0 1}
1: « AND »
VAR SCA.
1: {1 1 1 0 0 0 0 0}

2: {0 0 0 0 1 0 0 1}
1: « OR »
VAR SCA.
1: {0 0 0 0 1 1 1 1}

Lorsque l’opérateur f est commutatif (comme OR, AND, +, MAX…) il n’y a pas de différence entre le RPL et l’APL. Par contre, pour des opérateurs non commutatifs comme “<“, le résultat sera faux.

APL :   f\ a b c = (a) (a f b) (a f (b f c))

RPL :   f\ a b c = (a) (a f b) ((a f b) f c)

Pour se convaincre :

2: {0 0 1 0 1 1 0 0 1}
1: « < »
VAR SCA.
1: {0 0 0 0 0 0 0 0 0}

Résultat attendu : 0 0 1 0 0 0 0 0 0

Exercice – Les immeubles

On vous donne une liste de hauteurs d’immeubles adjacents et on vous demande combien seront visibles si vous les regardez à partir de la gauche. Par exemple, si les hauteurs sont 2 3 5 2 1 6 4, en vert ci-dessous les 4 seuls immeubles qui seront visibles (les autres sont cachés par des bâtiments plus hauts)

imm1

On supposera dans un premier temps qu’il n’y a pas de zones vides entre les immeubles, c’est-à-dire que la liste ne contient pas de 0 (immeubles de hauteur nulle).

IMM 2 3 5 2 1 6 4
Output: 4

Dans un second temps, considérez le cas général.

Corrigé version 1 : Commençons par l’APL. On va déjà scanner les immeubles pour récupérer les hauteurs maximales atteintes :

       ⌈\ 2 3 5 2 1 6 4
Output:   2 3 5 5 5 6 6

Il faut maintenant récupérer les hauteurs distinctes :

       ∪ ⌈\ 2 3 5 2 1 6 4
Output:     2 3 5 6

Et les compter :

⍴ ∪ ⌈\ 2 3 5 2 1 6 4
Output: 4

Le programme final en APL pour la version 1 :

IMM ← {⍴∪⌈\⍵}

Nous pouvons immédiatement traduire cela en RPL avec les programmes SCA. (scan), UN. (union) et la fonction SIZE :

« « MAX » SCA. UN. SIZE »
'IMM STO

Vérifions :

1: { 2 3 5 2 1 6 4 }
VAR IMM
1: 4.

Corrigé de la version générale : Si la liste commence par un ou plusieurs 0, le calcul sera faux :

1: { 0 2 1 }
VAR IMM
1: 2.

Ceci parce que les maximums progressifs sont { 0 2 2 } dont la réunion comporte 2 termes {0 2}. Il faut donc filtrer la liste des maximums pour enlever les 0. Une solution possible en APL :

IMM ← {⍴∪ (0 ≠ n) / n ← ⌈\⍵}

Et nous avions créer en RPL la fonction CL. pour compresser une liste en utilisant un vecteur logique. D’où cette version en RPL :

« « MAX » SCA. DUP 0 > CL. UN. SIZE »
'IMM STO

Qui signifie prendre les maximums progressifs, dupliquer cette liste, créer le vecteur logique des termes > 0, éliminer les éléments qui sont à FAUX, faire la réunion des éléments restants et les compter.

1: { 0 2 1 }
VAR IMM
1: 1.

Exemple – Les fractions continues

Pour la définition d’une fraction continue, voir par exemple Wikipedia.

En APL, on obtient la valeur approchée d’une liste d’étages par :

+∘÷/ 1 2 2 2 2
1.413793103

Qui correspond à la valeur 1 + 1 / ( 2 + 1 / ( 2 + 1 / ( 2 + 1 / 2 ) ) )

Et en utilisant un scan :

+∘÷\ 1 2 2 2 2
1 1.5 1.4 1.416666667 1.413793103

On obtient les fractions 1, puis 1 + 1 / 2 puis
1 + 1 / (2 + 1 / 2)…

En RPL, on peut obtenir la valeur finale par :

« REVLIST « OVER INV + » STREAM →NUM »
'FC STO

1: { 1 2 2 2 2 }
VAR FC
1: 1.41379310345     # ≃ racine de 2

1: { 1 1 1 1 1 1 1 1 1 1 }
VAR FC
1: 1.61818181818     # ≃ nombre d'or

L’opération “Prendre l’inverse plus additionner” n’étant pas commutative, on ne pourra pas utiliser notre fonction SCA.

Lire la suite…