Programmazione funzionale - Funzioni che definiscono la valutazione specifica delle funzioni passate ad essa per l'ottimizzazione

Naviga le tue risposte
4

In primo luogo, sono appena iniziato con la programmazione funzionale, quindi apprezzerei le correzioni in qualsiasi terminologia che potrei aver usato in modo errato.

Il tempo della storia, mentre facevo un Project Euler Problem 1 in Haskell, mi sono imbattuto in una soluzione simile a 

sum [3,6..999] + sum [5,10..999] - sum[15,30..999]

Quale somma viene valutata in 

foldl (+) [x1,x2,x3,x4,x5,x6,etc] -- yep, the sum is evaluated one element at a time

Quindi, la mia comprensione è che la valutazione lazy significa quella somma ( 2 ) potrebbe essere ottimizzato per modellare la corrispondenza con l'enumerazione ( 3 ) in modo che invece di piegarlo potrebbe ottimizzare per casi speciali come

Tuttavia,almenoinHaskell,nonèpossibileeseguireloschemadicorrispondenzaeacquisiregliargomentidaun'altrafunzione.L'ideadibasesarebbeselasommadebbaessereabbastanzaintelligentedariconoscerelaformulamatematicaconosciutaperl'ottimizzazionedelcalcolovalutandoaltrefunzionistesse:

--Doesn'twork;didn'tintendto;notvalidHaskell--Tryknownformulasfirstifthelistgeneratorisknown--Thiswouldmatchsum[1..100]andreturn5050inO(1)sum'EnumFromTo'1n=n*(n+1)/2--Ifthesumisnotrecognizedthenitwoulddoit1by1asafallbackinO(n)--Thisisthecurrentandonlyimplementationofsumsum=foldl(+)0

Direichesarebbepiùfacile,piùdirettoebetterstyledefinireunanuovafunzionedisommaconunnomediversochecopralaformuladatacome

sumTon|n>=1=n*(n+1)/2

Maconcettualmenteparlando

  • Èpossibileridefinirefunzionispecificheall'internodiun'altrafunzione?
  • Permetterebbequestapausaqualcosa?(IE,inquestocaso,"EnumFromTo 1 n" non verrebbe valutato, ma la somma restituirebbe comunque il risultato corretto)
  • Esistono esempi di questo schema di valutazione?
  • Questo è un concetto che implementa qualsiasi linguaggio di programmazione?
posta Fabián Heredia Montiel 26.05.2015 - 22:25
fonte

2 risposte

1

A causa del modo in cui l'espressione viene analizzata e valutata, una funzione sum otterrà i risultati di EnumFromTo , e quindi in condizioni normali non c'è modo di ottenere i suoi argomenti .

Per ricevere gli argomenti non valutati, devi utilizzare una macro . Non so nulla di Template Haskell , ma presumibilmente fornisce questa abilità. In pratica, le macro sono notoriamente difficili da usare al di fuori dei linguaggi omoiconici come LISP. La pigrizia di Haskell rimuove anche molti dei casi in cui le macro sarebbero utili. La tua funzione sumTo è molto più facile da implementare, quindi è quello che useranno le persone.

    
risposta data 27.05.2015 - 00:11
fonte
-2

Controlla questo (codice Clojure, mi dispiace non conosco Haskell): 

(declare m-enum-upto)

(defn enum-upto [n]
  (cond
    (= n 0) 0
    (= n 1) 1
    :else (+ n (m-enum-upto (dec n)))))

(def m-enum-upto (memoize enum-upto))

; at the first run 
(enum-upto 5) ; 0.497711 msec
;again
(enum-upto 5); 0.1130686 msec
;and now
(enum-upto 3); 0.09372 msec
(enum-upto 30); 0.883901 msec
(enum-upto 5); 0.100872 msec
(enum-upto 20); 0.100515 msec

Il trucco sta usando memoize, usa una cache per memorizzare i valori di enum-upto. In questo modo devono essere calcolati solo nuovi valori.

oppure potresti usare riduttori:

(defn r-enum-upto [n] (riduci + (map inc (range n))))

(r-enum-fino a 200); 0,18883 msec (r-enum-fino a 200000); 43.050614 msec

Spero che aiuti!

    
risposta data 26.05.2015 - 23:24
fonte

Leggi altre domande sui tag

Esiste un nome per il concetto di "somma cumulativa"? [chiuso] Funzioni di concatenamento nei linguaggi procedurali [duplicato]