Quali sono i termini di programmazione funzionale corretta per ciò che sto facendo qui?

4

Recentemente ho avuto bisogno di una funzione per clonare in profondità un oggetto. Ho iniziato con il codice fornito come risposta accettata a questa domanda: link

Tuttavia, il nostro SonarQube si è lamentato del fatto che la funzione fosse troppo complessa, a causa delle molteplici istruzioni if. Così ho refactored il codice a questo:

function getContainer(input) {
    return input.isContainer ? input : {
        isContainer: true,
        isDone: false,
        value: input
    };
}

function processor(isApplicable, process) {
    return input => {
        const container = getContainer(input);
        const { isDone, value } = container;
        if (isDone) {
            return container;
        }
        if (isApplicable(value)) {
            return Object.assign({}, container, {
              value: process(value),
              isDone: true
            });
        }
        return container;
    };
}

const processNoObject = processor(isNoObject, cloneNoObject);
const processDate = processor(isDate, cloneDate);
const processMap = processor(isMap, cloneMap);
const processArray = processor(isArray, cloneArray);
const processObject = processor(isObject, cloneObject);

function clone(input) {
    const { isDone, value } = processNoObject(processDate(processMap(processArray(processObject(input)))));
    if (isDone) {
        return value;
    }
    throw new Error('Unable to copy object! Its type isn\'t supported');
}

Ho omesso le funzioni isObject, cloneObject, ecc. qui per brevità. Il codice completo di lavoro può essere trovato qui: link

Quali sono i termini FP corretti per ciò che ho chiamato "processore" e "contenitore" nel mio codice? Suppongo che il processore sia qualcosa come una monade, ma non ne sono sicuro.

    
posta Patrick Hund 26.02.2017 - 13:36
fonte

2 risposte

5

Queste non sono monade, perché non hai specificato un insieme di operazioni ("unità", "flatMap") che soddisfano le leggi della monade. Tuttavia, il tuo design è chiaramente ispirato alle monadi, con una funzione che racchiude un valore in un contenitore e una funzione che solleva altre funzioni dal livello di valore a livello di contenitore.

Per una monade, abbiamo bisogno di un costruttore (value) -> Container e un'operazione flatMap (Container, (value) -> Container) -> Container . Il tuo contenitore ha due possibili casi (isDone e non isDone). Questo potrebbe essere implementato come:

function Container(value) {  // this is the constructor
  return {
    value: value,
    isDone: false,
    flatMap: function flatMap (f) { return f(value) },
  };
}

function ContainerIsDone(value) {
  return {
    value: value,
    isDone: true,
    flatMap: function flatMap (f) { return this },
  };
}

Per comodità, flatMap è stato creato qui come metodo invece di una funzione gratuita.

Se questo soddisfa le leggi della monade (e lo fa), allora:

  • ha lasciato l'identità: Container(x).flatMap(f) === f(x) per tutti i valori x e per tutte le funzioni idonee f .
  • ha la giusta identità: c.flatMap(Container) === c per tutti i contenitori c .
  • è associativo: c.flatMap(f).flatMap(g) === c.flatMap(x => f(x).flatMap(g)) per tutti i contenitori c e funzioni appropriate f, g .

Il tuo processor ora può essere espresso come:

function processor(isApplicable, process) {
  return container => container.flatMap(value => {
    if (isApplicable(value))
      return ContainerIsDone(process(value));
    return Container(value);
  });
}

E la tua pipeline sarebbe:

const { value, isDone } = processNoObject(...(Container(input)...);
...

Invece di sillabare la pipeline come chiamate di funzioni nidificate, potremmo usare Array#reduce() :

const pipeline = [processObject, ..., processNoObject];
const { value, isDone } = pipeline.reduce((c, processor) => processor(c), Container(input));

Il che significa che non abbiamo necessariamente bisogno del costruttore processor :

const pipeline = [
  [isObject, cloneObject],
  ...,
  [isNoObject, cloneNoObject],
];

let container = Container(input);
for (const [isApplicable, process] of pipeline) {
  container = container.flatMap(value => {
    if (isApplicable(value))
      return ContainerIsDone(process(value));
    return Container(value);
  });
}

const { value, isDone } = container;
if (isDone)
  return value;
throw new Error(...);

Il che significa che non abbiamo davvero bisogno di nessuno di questi contenitori e altre astrazioni affatto :

const pipeline = [
  [isObject, cloneObject],
  ...,
  [isNoObject, cloneNoObject],
];

for (const [isApplicable, process] of pipeline) {
  if (isApplicable(input))
    return process(input);
}

throw new Error(...);

Che ha un valore dubbio a meno che la pipeline non sia configurata dinamicamente. Probabilmente, srotolando quel loop su semplici condizioni sarà più chiaro:

if (isObject(input)) return cloneObject(input);
...
if (isNoObject(input)) return cloneNoObject(input);
throw new Error(...);

Anche se SonarCube si lamenta, un'implementazione così semplice è molto più utile per la comprensione umana piuttosto che introdurre astrazioni extra come nascondere il reale flusso di controllo nelle strutture dati. Per questo problema, la programmazione funzionale probabilmente non è una risposta adatta poiché la programmazione procedurale è totalmente sufficiente.

    
risposta data 26.02.2017 - 15:16
fonte
2

La risposta di amon è abbastanza buona, e in generale sono d'accordo con la conclusione che in questo caso una semplice sequenza di affermazioni if è più chiara. Tuttavia, penso che il tuo codice colpisca una tecnica importante che vorrei associare al programma funzionale, cioè codificare il flusso di controllo del programma nelle sue strutture dati. Al suo estremo, sembra strutturare il tuo programma come un interprete su un ADT. Abbiamo un caso più mite qui.

Se guardiamo il tuo tipo container , è essenzialmente (Boolean, Object) . Molto spesso però, questi tipi di prodotti vogliono davvero essere dei tipi di somma e semplicemente non hanno il supporto linguistico. Quindi penso che un rendering corretto (scegliendo Haskell come lingua di arrivo) sia qualcosa come

data Container a b = Done a | Ongoing b

I risultati della funzione del processore sono di tipo

type Processor a b = Container a b -> Container a b

E definito dal seguente

processor :: (b -> Boolean) -> (b -> a) -> Processor a b
processor isApplicable f = \ container -> case container of 
    Done a    -> Done a
    Ongoing b -> if isApplicable a then Done (f b) else Ongoing b

Ora possiamo vedere che i risultati di processor hanno sempre un punto fisso a Done a . In effetti, parte della nostra intenzione nel chiamarla Done era di suggerire che rappresenta la fine di un calcolo. Possiamo rappresentare questo suggerimento introducendo una funzione di ordine superiore che riflette ciò.

mapContainer :: (b -> c) -> Container a b -> Container a c
mapContainer f (Done a) = Done a
mapContainer f (Ongoing b) = Ongoing (f b)

In genere chiamiamo mapContainer fmap come (Container a, mapContainer) forma un functor come

mapContainer id == id
mapContainer (f . g) == mapContainer f . mapContainer g

Quindi scriveremmo

instance Functor (Container a) where
    fmap = mapContainer

Ora possiamo riscrivere processor per utilizzare fmap .

processor isApplicable f = \ container -> 
    case fmap (\b -> if isApplicable b then Done (f b) else Ongoing b) of
        Done a -> Done a
        Ongoing (Done a) -> Done a
        Ongoing (Ongoing b) -> Ongoing b

In realtà sembra un po 'peggio, ma ci stiamo avvicinando. Il passaggio successivo consiste nel notare che il bit nel mezzo rappresenta un altro suggerimento che vogliamo esprimere su Container oggetti, ovvero che quando colpiamo Done in qualsiasi punto di uno stack, abbiamo finito per sempre.

joinContainer :: Container a (Container a b) -> Container a b
joinContainer (Done a) = Done a
joinContainer (Ongoing (Done a)) = Done a
joinContainer (Ongoing (Ongoing b)) = Ongoing b

Ora possiamo scrivere processor come

processor isApplicable f = join . fmap (\b -> isApplicable b then Done (f b) else Ongoing b)

Ora, quelli con alcune classi di tipi sotto la cintura riconosceranno la somiglianza tra joinContainer e join . E una volta che ci rendiamo conto che abbiamo una funzione return in Ongoing sappiamo che abbiamo abbastanza per dichiarare Container una monade.

instance Monad (Container a) where
    return = Ongoing
    c >>= f = joinContainer (mapContainer f c)

Ora possiamo riscrivere il processore come

processor isApplicable f = \ c -> c >>= (\b -> if isApplicable b then Done (f b) else Ongoing b)

Quindi abbiamo trovato la monade al centro del tuo programma. Ora come suggerisce @amon, possiamo riscrivere la tua funzione clone essenzialmente rimuovendo un po 'di colla. In questo momento clone assomiglia a

clone c = let c' = processor isNoObject cloneNoObject . processor isDate cloneDate . ... . processor isObject cloneObject $ return c
    in case c' of 
        Done a -> a
        Ongoing _ -> error ""

Che espanso appare come

clone c = let c' = return c >>= (\b -> if isObject b then Done (cloneObject b) else Ongoing b) >>= ... >>= (\b -> if isNoObject b then Done (cloneNoObject b) else Ongoing b)
    in case c' of
        Done a -> a
        Ongoing _ -> error ""

Ora le cose diventano molto più gestibili se invece di calcolare la parte >>= (\b -> ...) è sufficiente calcolare la parte (\b -> ...) .

processor' isApplicable f b 
    | isApplicable b = Done (f b)
    | otherwise      = Ongoing b

Quindi possiamo scrivere

clone c = let c' = (do
        object <- processor' isObject cloneObject c
        ...
        noObject <- processor' isNoObject cloneNoObject date
        return noObject)
    in case c' of 
        Done a -> a
        Ongoing _ -> error ""

E ora possiamo ricostituire processor isX cloneX come una freccia di Kleisi e riscrivere clone ancora una volta con > = > (composizione freccia di Kleisi).

clone c = let c' = processor' isObject cloneObject >=> ... >=> processor' isNoObject cloneNoObject $ c
    in case c' of 
        Done a -> a
        Ongoing _ -> error ""

Ora può sembrare che tutto ciò che abbiamo fatto sia aumentato l'oscurità del nostro codice. In generale, tuttavia, penso che spostare la logica di ramificazione del programma dal livello di superficie nei tipi di dati e combinatori sia vantaggioso a lungo termine 1. implementando un pensiero algebrico e 2. fornendo maggiore rigidità nei flussi di controllo.

Potremmo vedere il pensiero algebrico svilupparsi durante questo processo quando abbiamo scoperto come potremmo esprimere le caratteristiche del nostro programma come caratteristiche delle nostre strutture dati di base; in questo processo abbiamo visto che il cortocircuito e l'unione avvenuta nel nostro programma ci hanno spinti naturalmente verso operazioni sui nostri contenitori che le incarnavano. Abbiamo anche notato che queste operazioni si adattano alle astrazioni di tipo, ovvero Functional and Monads.

Sembra strano pensare a flussi di controllo più rigidi come un vantaggio nella programmazione: sicuramente la flessibilità è sempre una buona cosa? Ma i vincoli hanno un lato positivo; le lingue moderne hanno eliminato gradualmente goto per un motivo. In generale, penso alla programmazione funzionale come ulteriore progresso lungo la programmazione strutturale: invece di usare i nostri costrutti strutturati if e while , preferiamo definire tipi e funzioni di ordine superiore che rappresentano flussi di controllo più astratti. Quando le cose sono scritte in questo modo, il nostro codice può diventare molto più facile da leggere e diventa più difficile introdurre nuove complessità.

Come una nota vagante: il tipo Container è molto meglio conosciuto con il suo nome comune Either ( Either è solitamente pensato come rappresentazione di calcoli che possono fallire ma è più accurato pensarlo come incarnante corto circuiting in generale).

    
risposta data 28.02.2017 - 06:48
fonte

Leggi altre domande sui tag