Programmazione funzionale: confronta tutti gli elementi in una matrice

Voglio rispondere a una piccola parte della tua domanda, che è comunque molto interessante:

Is it possible to use a fold (also known as reduce) operation for this?

Sì, lo è.

In effetti, è sempre possibile usare una piega per qualsiasi cosa ! Fold è un'operazione generale per l'iterazione, qualsiasi cosa puoi fare con l'iterazione, puoi farlo con fold!

La pagina di Wikipedia per la piega ha uno schizzo di prova per questo, ma io voglio dare un'altra intuizione grazie a un discorso di Rúnar Óli Bjarnason su Programmazione funzionale per principianti che sfortunatamente sembra essere svanita dall'interweb.

Una raccolta può essere vuota o non vuota. I due argomenti da piegare indicano cosa fare quando la raccolta è vuota e cosa fare con l'elemento successivo quando la raccolta non è vuota. Ciò copre tutti i casi, quindi dovrebbe essere intuitivamente chiaro che quella piega può fare qualsiasi cosa .

Un'altra vista, grazie a quello stesso discorso, è di piegare come interprete. Pensa a una collezione come a una serie di istruzioni. Esistono due tipi di istruzioni: l'istruzione HALT (che non ha operandi) e l'istruzione NEXT , che ha un operando. I due argomenti che fornisci per passare, sono le due implementazioni delle funzioni dell'interprete per HALT e NEXT . Di nuovo, dato che ci sono solo due istruzioni e tu fornisci il codice per entrambi, non sorprende che quella piega possa fare qualsiasi cosa.

In realtà l'ho messo alla prova e ha riutilizzato molti dei metodi dal framework di raccolta di Ruby (la Enumerable module), che normalmente si basano only sul metodo each (un foreach -style iterator che restituisce semplicemente ogni elemento), in modo che invece si basino tutti sul metodo inject ( che è il modo in cui gli incantesimi di Ruby si "piegano").

Quindi, che fa ha l'aspetto di una piega in ECMAScript?

someArray.reduce((memo, el, i, ary) => memo && ary[0] === el, true)

Tuttavia, solo perché fold può fare tutto, non dovrebbe essere usato per tutto. Quando ci sono operazioni più appropriate e più specializzate, queste dovrebbero essere invece utilizzate:

someArray.every((el, i, ary) => ary[0] === el)

Nota: tecnicamente parlando, queste due implementazioni non controllano se ogni elemento è uguale a ogni altro elemento, controllano solo se ogni elemento è uguale al primo elemento. Quindi, si basa su === che è transitivo e simmetrico (come dovrebbe essere un'eguaglianza ben condotta). Se non puoi fare affidamento su questo, devi prima costruire il prodotto cartesiano dell'array con se stesso, mapparlo per stabilire se i due elementi sono uguali e poi chiedere se è tutto vero:

someArray.reduce((memo, el, _, ary) => memo.concat(ary.map(ell => [el, ell])), []).
map(([a, b]) => a === b).
every(el => el)

Bene, ho più di 10 anni di esperienza nella programmazione funzionale, ed ecco come lo farei io:

1. Se la sequenza è vuota, restituisce true
2. Altrimenti, restituisce true se e solo se tutti gli elementi della sequenza sono uguali al primo.

In Haskell, che inizia così:

-- | Return false if and only if there is a pair of unequal elements
-- in the list.
allEqual :: Eq a => [a] -> a
allEqual [] = True
allEqual (first:rest) = all (\elem -> elem == first) rest

La funzione all verifica se tutti gli elementi di un elenco soddisfano una condizione specificata. In questo caso, la condizione è (\elem -> elem == first) , una funzione che verifica se il dato elem è uguale a first .

La funzione all è fornita in modulo di libreria Data.List , ma implementiamolo da soli:

-- | Apply the given test to every element in the list, and return
-- false if and only if at least one element tests false.
all :: (a -> Bool) -> [a] -> Bool
all test items = and (map test items)

Per implementare all ho usato altre due funzioni standard- map e and . Ma andiamo e implementiamo noi stessi:

-- | Return true if and only if there are no 'False' elements in the list
and :: [Bool] -> Bool
and bools = foldr (&&) True bools

-- | Apply the given function to all elements of the list, collecting
-- the results in a list.
map :: (a -> b) -> [a] -> [b]
map f = foldr go []
  where go item rest = f item : rest

E quelle due funzioni che ho scritto in termini di foldr ("fold right"), che è una di queste "riduci" l'operazione a cui sei interessato. Per completezza, scriviamo quella funzione:

foldr :: (a -> r -> r) -> r -> [a] -> r
foldr _ z [] = z
foldr f z (a:as) = f a (foldr f z as)

E ora lasciatemi indicare qualcosa di molto importante che ho fatto: Ho scritto la funzione che volevi in termini di funzione di utilità, che ho poi scritto in termini di due ulteriori funzioni di utilità, che ho poi scritto in termini di foldr , che ho poi scritto . Inoltre, poiché la libreria fornisce tutte quelle funzioni di utilità, avrei potuto semplicemente fermarmi alla prima definizione.

Questa è una cosa fondamentale che i nuovi arrivati alla programmazione funzionale spesso trascurano-riduci / piega è un'operazione di basso livello che usi per scrivere una grande libreria di operazioni ausiliarie più facili da usare e ti abbatti i tuoi problemi in termini di quelli. Guarda ad esempio il gran numero di funzioni presenti nel modulo di libreria Data.List di Haskell .

Il modo in cui ottieni una buona elaborazione dell'elenco in stile funzionale è:

1. Scopri come abbattere i problemi in termini di funzioni di libreria come quelle;
2. Scopri come scrivere quelle funzioni della libreria o quelle nuove e simili che mancano dalla libreria.

Se raggiungi sempre per reduce , finirai con il codice che è più difficile da scrivere e da leggere. Mentre le utility riutilizzabili funzionano normalmente per risolvere questo problema, l'ultima riga della mia definizione di allEqual si legge fondamentalmente in questo modo: "verifica se tutti gli elementi dopo il primo nell'elenco sono uguali ad esso."

La maggior parte dei linguaggi FP che ho visto hanno un'implementazione di fold / reduce che accetta un valore iniziale per un accumulatore, ad es. in Haskell:

pairs = zipWith (,) xs ys
foldl (\accum (x,y) -> (x == y) && accum) True pairs
---------------------------- initial value ^

Di solito ci sono anche altre funzioni che si occupano di calcoli come questo, come and :

and [True,False,True,True,False] == False