Existe-t-il un moyen de représenter élégamment ce modèle en Haskell ?

Question

Pensez à la fonction pure ci-dessous, dans un langage impératif :

def foo(x,y):
    x = f(x) if a(x)
    if c(x): 
        x = g(x)
    else:
        x = h(x)
    x = f(x)
    y = f(y) if a(y)
    x = g(x) if b(y)
    return [x,y]

Cette fonction représente un style où vous devez mettre à jour les variables de manière incrémentielle. On peut l'éviter dans la plupart des cas, mais il existe des situations où ce modèle est inévitable - par exemple, l'écriture d'une procédure de cuisson pour un robot, qui nécessite par nature une série d'étapes et de décisions. Maintenant, imaginons que nous essayions de représenter foo en Haskell.

foo x0 y0 =
    let x1 = if a x0 then f x0 else x0 in
    let x2 = if c x1 then g x1 else h x1 in
    let x3 = f x2 in
    let y1 = if a y0 then f y0 else y0 in
    let x4 = if b y1 then g x3 else x3 in
    [x4,y1]

Ce code fonctionne, mais il est trop compliqué et sujettes à des erreurs en raison de la nécessité de gérer manuellement les étiquettes numériques. Remarquez que, après x1 est réglé, x0 La valeur de l'entreprise ne devrait plus jamais être utilisée, mais elle peut toujours l'être. Si vous l'utilisez accidentellement, ce sera une erreur non détectée.

J'ai réussi à résoudre ce problème en utilisant la monade State :

fooSt x y = execState (do
    (x,y) <- get
    when (a x) (put (f x, y))
    (x,y) <- get
    if c x 
        then put (g x, y) 
        else put (h x, y)
    (x,y) <- get
    put (f x, y)
    (x,y) <- get
    when (a y) (put (x, f y))
    (x,y) <- get
    when (b y) (put (g x, x))) (x,y)

De cette façon, le besoin de suivi des balises disparaît, de même que le risque d'utiliser accidentellement une variable obsolète. Mais maintenant le code est verbeux et beaucoup plus difficile à comprendre, principalement à cause de la répétition de (x,y) <- get .

Donc : quelle est une manière plus lisible, plus élégante et plus sûre d'exprimer ce modèle ? ?

Code complet pour les tests.

Answer 1

Vos objectifs

Alors que la transformation directe d'un code impératif conduirait généralement à la ST et la monade STRef réfléchissons à ce que vous voulez vraiment faire :

1. Vous voulez manipuler des valeurs de manière conditionnelle.
2. Vous voulez renvoyer cette valeur.
3. Vous voulez séquencer les étapes de votre manipulation.

Exigences

Maintenant, cela ressemble en effet d'abord à la ST monade. Cependant, si l'on suit les lois de la monade simple, avec do nous voyons que

do 
   x <- return $ if somePredicate x then g x
                                    else h x
   x <- return $ if someOtherPredicate x then a x
                                         else b x

est exactement ce que vous voulez. Puisque vous n'avez besoin que des fonctions les plus élémentaires d'une monade ( return et >>= ), vous pouvez utiliser le plus simple :

Le site Identity monade

foo x y = runIdentity $ do
    x <- return $ if a x then f x
                         else x
    x <- return $ if c x then g x
                         else h x
    x <- return $ f x 
    y <- return $ if a x then f y
                         else y
    x <- return $ if b y then g x
                         else y
    return (x,y)

Notez que vous ne pouvez pas utiliser let x = if a x then f x else x car dans ce cas, le x serait le même des deux côtés, alors que

x <- return $ if a x then f x 
                     else x

est la même chose que

(return $ if a x then (f x) else x) >>= \x -> ...

et le x dans le if n'est clairement pas la même que celle qui en résulte, qui va être utilisée dans la lambda de droite.

Aides

Afin de rendre cela plus clair, vous pouvez ajouter des aides telles que

condM :: Monad m => Bool -> a -> a -> m a
condM p a b = return $ if p then a else b

pour obtenir une version encore plus concise :

foo x y = runIdentity $ do
    x <- condM (a x) (f x) x
    x <- fmap f $ condM (c x) (g x) (h x)    
    y <- condM (a y) (f y) y
    x <- condM (b y) (g x) x
    return (x , y)

La folie ternaire

Et pendant que nous y sommes, augmentons la folie et introduisons un opérateur ternaire :

(?) :: Bool -> (a, a) -> a
b ? ie = if b then fst ie else snd ie

(??) :: Monad m => Bool -> (a, a) -> m a
(??) p = return . (?) p

(#) :: a -> a -> (a, a)
(#) = (,)

infixr 2 ??
infixr 2 #
infixr 2 ?

foo x y = runIdentity $ do
    x <- a x ?? f x # x
    x <- fmap f $ c x ?? g x # h x
    y <- a y ?? f y # y
    x <- b y ?? g x # x
    return (x , y)

Mais l'essentiel est que le Identity a tout ce dont vous avez besoin pour cette tâche.

Impératif ou non-impératif

On peut se demander si ce style est impératif. Il s'agit bien d'une séquence d'actions. Mais il n'y a pas d'état, sauf si l'on compte les variables liées. Cependant, alors un paquet de let … in … donne également une séquence implicite : vous vous attendez à ce que la première let à lier en premier.

Utilisation de Identity est purement fonctionnelle

Dans tous les cas, le code ci-dessus n'introduit pas de mutabilité. x n'est pas modifié, au lieu de cela vous avez une nouvelle x ou y ombrageant le dernier. Cela devient clair si vous désugarisez le do comme indiqué ci-dessus :

foo x y = runIdentity $
      a x ?? f x # x   >>= \x ->
      c x ?? g x # h x >>= \x ->
      return (f x)     >>= \x ->
      a y ?? f y # y   >>= \y ->
      b y ?? g x # x   >>= \x ->
      return (x , y)

Se débarrasser de la monade la plus simple

Cependant, si nous utilisions (?) sur le côté gauche et retirez le return nous pourrions remplacer (>>=) :: m a -> (a -> m b) -> m b) par quelque chose de type a -> (a -> b) -> b . Il se trouve que c'est flip ($) . Nous nous retrouvons avec :

($>) :: a -> (a -> b) -> b
($>) = flip ($)     
infixr 0 $> -- same infix as ($)

foo x y = a x ? f x # x   $> \x ->
          c x ? g x # h x $> \x ->
          f x             $> \x ->
          a y ? f y # y   $> \y ->
          b y ? g x # x   $> \x ->
          (x, y)

C'est très similaire au désucré do ci-dessus. Notez que toute utilisation de Identity peut être transformé en ce style, et vice-versa.

Answer 2

Le problème que vous énoncez ressemble à une belle application pour flèches :

import Control.Arrow

if' :: (a -> Bool) -> (a -> a) -> (a -> a) -> a -> a
if' p f g x = if p x then f x else g x

foo2 :: (Int,Int) -> (Int,Int)
foo2 = first (if' c g h . if' a f id) >>>
       first f >>>
       second (if' a f id) >>>
       (\(x,y) -> (if b y then g x else x , y))

en particulier, first lève une fonction a -> b à (a,c) -> (b,c) ce qui est plus idiomatique.

Edit : if' permet une levée

import Control.Applicative (liftA3)

-- a functional if for lifting
if'' b x y = if b then x else y

if' :: (a -> Bool) -> (a -> a) -> (a -> a) -> a -> a
if' = liftA3 if''

Answer 3

Je ferais probablement quelque chose comme ça :

foo x y = ( x', y' )
  where x' = bgf y' . cgh . af $ x
        y' = af y

af z    = (if a z then f else id) z
cgh z   = (if c z then g else h) z
bg y x  = (if b y then g else id) x

Pour quelque chose de plus compliqué, vous pouvez envisager d'utiliser une lentille :

whenM :: Monad m => m Bool -> m () -> m ()
whenM c a = c >>= \res -> when res a

ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM mb ml mr = mb >>= \b -> if b then ml else mr

foo :: Int -> Int -> (Int, Int)
foo = curry . execState $ do
  whenM (uses _1 a) $ 
    _1 %= f

  ifM (uses _1 c)
    (_1 %= g)
    (_1 %= h)

  _1 %= f

  whenM (uses _2 a) $ 
    _2 %= f

  whenM (uses _2 b) $ do
    _1 %= g

Et rien ne vous empêche d'utiliser des noms de variables plus descriptifs :

foo :: Int -> Int -> (Int, Int)
foo = curry . execState $ do
  let x :: Lens (a, c) (b, c) a b
      x = _1
      y :: Lens (c, a) (c, b) a b
      y = _2

  whenM (uses x a) $ 
    x %= f

  ifM (uses x c)
    (x %= g)
    (x %= h)

  x %= f

  whenM (uses y a) $ 
    y %= f

  whenM (uses y b) $ do
    x %= g

Answer 4

C'est un travail pour les ST (transformateur d'état).

ST fournit :

• Calculs avec état sous la forme de la ST type. Ils se présentent comme suit ST s a pour un calcul qui aboutit à une valeur de type a et peut être exécuté avec runST pour obtenir un pur a valeur.
• Références mutables de première classe sous la forme de la STRef type. Le site newSTRef a crée une nouvelle STRef s a avec une valeur initiale de a et qui peut être lu avec readSTRef ref et écrit avec writeSTRef ref a . Un seul calcul ST peut utiliser un nombre quelconque de références STRef en interne.

Ensemble, ils vous permettent d'exprimer la même fonctionnalité de variable mutable que dans votre exemple impératif.

Pour utiliser ST et STRef, nous devons procéder à une importation :

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Monad.ST.Safe
import Data.STRef

Au lieu d'utiliser l'option de bas niveau readSTRef et writeSTRef partout, nous pouvons définir les aides suivantes pour correspondre aux opérations impératives que le langage de style Python foo exemple d'utilisation :

-- STRef assignment.
(=:) :: STRef s a -> ST s a -> ST s ()
ref =: x  =  writeSTRef ref =<< x

-- STRef function application.
($:) :: (a -> b) -> STRef s a -> ST s b
f $: ref  =  f `fmap` readSTRef ref

-- Postfix guard syntax.
if_ :: Monad m => m () -> m Bool -> m ()
action `if_` guard  =  act' =<< guard
    where act' b = if b then action
                        else return ()

Cela nous permet d'écrire :

• ref =: x pour attribuer la valeur du calcul de ST x au STRef ref .
• (f $: ref) pour appliquer une fonction pure f au STRef ref .
• action `if_` guard d'exécuter action seulement si guard donne le résultat Vrai.

Avec ces aides en place, nous pouvons traduire fidèlement la définition impérative originale de foo en Haskell :

a = (< 10)
b = even
c = odd
f x = x + 3
g x = x * 2
h x = x - 1
f3 x = x + 2

-- A stateful computation that takes two integer STRefs and result in a final [x,y].
fooST :: Integral n => STRef s n -> STRef s n -> ST s [n]
fooST x y = do
    x =: (f $: x) `if_` (a $: x)

    x' <- readSTRef x
    if c x' then
        x =: (g $: x)
    else
        x =: (h $: x)

    x =: (f $: x)
    y =: (f $: y) `if_` (a $: y)
    x =: (g $: x) `if_` (b $: y)

    sequence [readSTRef x, readSTRef y]

-- Pure wrapper: simply call fooST with two fresh references, and run it.
foo :: Integral n => n -> n -> [n]
foo x y = runST $ do
    x' <- newSTRef x
    y' <- newSTRef y
    fooST x' y'

-- This will print "[9,3]".
main = print (foo 0 0)

Points à noter :

• Bien que nous ayons d'abord dû définir quelques aides syntaxiques ( =: , $: , if_ ) avant de traduire foo Ce document montre comment vous pouvez utiliser ST et STRef comme base pour développer votre propre petit langage impératif, directement adapté au problème à résoudre.
• En dehors de la syntaxe, cela correspond exactement à la structure de la définition impérative originale, sans aucune restructuration susceptible d'entraîner des erreurs. Toutes les modifications mineures apportées à l'exemple original peuvent être transposées directement en Haskell. (L'ajout de l'élément temporaire x' <- readSTRef x dans le code Haskell ne sert qu'à l'utiliser avec la syntaxe if/else native : si on le souhaite, elle peut être remplacée par une construction if/else appropriée basée sur ST).
• Le code ci-dessus montre qu'il est possible d'offrir des interfaces pures et dynamiques pour le même calcul : les appelants purs peuvent utiliser la fonction foo sans savoir qu'il utilise un état mutable en interne, alors que ST les appelants peuvent utiliser directement fooST (et par exemple lui fournir des STRefs existants à modifier).

Answer 5

@Sibi l'a bien dit dans son commentaire :

Je vous suggère d'arrêter de penser de manière impérative et de penser plutôt de manière fonctionnelle. Je reconnais qu'il faudra un certain temps pour s'habituer au nouveau modèle, mais essayer de traduire des idées impératives en langages fonctionnels n'est pas une bonne approche.

En pratique, votre chaîne de let peut être un bon point de départ :

foo x0 y0 =
    let x1 = if a x0 then f x0 else x0 in
    let x2 = if c x1 then g x1 else h x1 in
    let x3 = f x2 in
    let y1 = if a y0 then f y0 else y0 in
    let x4 = if b y1 then g x3 else x3 in
    [x4,y1]

Mais je suggère d'utiliser un seul let et en donnant des noms descriptifs aux étapes intermédiaires.

Dans cet exemple, je n'ai malheureusement pas la moindre idée de ce que font les différents x et y, et je ne peux donc pas suggérer de noms significatifs. Dans un code réel, vous utiliseriez des noms tels que x_normalized , x_translated ou autre, au lieu de x1 et x2 pour décrire ce que sont réellement ces valeurs.

En fait, dans un let ou where vous n'avez pas vraiment de variables : ce ne sont que des noms abrégés que vous donnez aux résultats intermédiaires, pour faciliter la composition de l'expression finale (celle après in ou avant le where .)

C'est l'esprit qui sous-tend le x_bar et x_baz ci-dessous. Essayez de trouver des noms qui soient raisonnablement descriptifs, compte tenu du contexte de votre code.

foo x y =
    let x_bar   = if a x then f x else x
        x_baz   = f if c x_bar then g x_bar else h x_bar
        y_bar   = if a y then f y else y
        x_there = if b y_bar then g x_baz else x_baz
    in  [x_there, y_bar]

Vous pouvez alors commencer à reconnaître les modèles qui étaient cachés dans le code impératif. Par exemple, x_bar et y_bar sont fondamentalement la même transformation, appliquée respectivement à x et y c'est pourquoi ils ont le même suffixe "_bar" dans cet exemple absurde ; alors votre x2 n'a probablement pas besoin d'un nom intermédiaire, puisque vous pouvez simplement appliquer f au résultat de l'ensemble du "if c then g else h".

En poursuivant la reconnaissance des formes, vous devez factoriser les transformations que vous appliquez aux variables dans des sous-lambdas (ou quel que soit le nom que vous donnez aux fonctions auxiliaires définies dans un fichier where clause.)

Encore une fois, je n'ai pas la moindre idée de ce que faisait le code original, et je ne peux donc pas suggérer de noms significatifs pour les fonctions auxiliaires. Dans une application réelle, f_if_a s'appellerait normalize_if_needed ou thaw_if_frozen ou mow_if_overgrown ... vous voyez l'idée :

foo x y =
    let x_bar   = f_if_a x
        y_bar   = f_if_a y
        x_baz   = f (g_if_c_else_h x_bar)
        x_there = g_if_b x_baz y_bar
    in  [x_there, y_bar]
where
    f_if_a x
        | a x       = f x
        | otherwise = x
    g_if_c_else_h x
        | c x       = g x
        | otherwise = h x
    g_if_b x y
        | b y       = g x
        | otherwise = x

Ne négligez pas cette activité de dénomination.

L'intérêt de Haskell et des autres langages fonctionnels purs est d'exprimer des algorithmes sans l'opérateur d'affectation, c'est-à-dire l'outil qui permet de modifier la valeur d'une variable existante.

Les noms que vous donnez aux choses à l'intérieur d'une définition de fonction, qu'elles soient introduites comme arguments, let ou where La définition de la fonction auxiliaire ne peut faire référence qu'à une seule valeur (ou fonction auxiliaire) dans toute la définition, de sorte que votre code peut être plus facilement raisonné et prouvé correct.

Si vous ne leur donnez pas de noms significatifs (et inversement, si vous ne donnez pas à votre code une structure significative), vous passez à côté de l'objectif principal de Haskell.

(À mon avis, les autres réponses données jusqu'à présent, qui citent les monades et d'autres manigances, ne vont pas dans le bon sens).