Qual è la ragione della complessità algoritmica in Haskell?

Question

Qual è la ragione della complessità algoritmica in Haskell?

#1 da (3 voti)

7

In Haskell, la valutazione lenta può essere spesso utilizzata per eseguire calcoli efficienti di espressioni scritte in modo chiaro e conciso. Tuttavia, sembra che il linguaggio stesso non fornisca abbastanza dettagli per determinare, in generale, le esigenze di tempo e spazio di un dato pezzo di codice. La situazione sembra essere mitigata, in una certa misura, dall'uso comune di ghc, che raccolgo fornisce alcune garanzie più specifiche relative alla forma debole-testa-normale. Ma se non sbaglio, l'effettiva esecuzione del codice può essere ancora abbastanza difficile da capire.

Ad esempio, utilizziamo anche il polimorfismo per esprimere le funzioni in modo generico, sempre senza sacrificare la chiarezza. Tuttavia, quando combinato con strutture ponderate, le due caratteristiche linguistiche sembrano interagire in modi che sono (per me) sorprendenti. Prendere in considerazione:

import Debug.Trace (trace)
tracePlus a b = trace (show a ++ "+" ++ show b) (a+b)
    -- This lets us try small integers to see how things get evaluated.
    -- Those tests can thereby reveal the asymptotic behavior of the code, without 
    -- needing to actually try bigger values.

class Sum a where
    one :: a
    add :: a -> a -> a

instance Sum Integer where
    one = 1
    add = tracePlus

fibSums_list :: (Sum a) => [a]
fibSums_list = one : one : zipWith add fibSums_list (tail fibSums_list)

fibS :: Int -> Integer
fibS = (fibSums_list !!)

Devo notare che funziona bene se lo compilo con ghc -O2 . Tuttavia, se eseguito in ghci , richiede una complessità temporale esponenziale per valutare fibS . Tuttavia, l'uso di un elenco di numeri di Fibonacci di tipo [Integer] funziona bene pure.

Quindi, una domanda specifica che ho è: c'è un modo per riscrivere fibSums_list e / o fibS , in modo che mantenga l'uso della classe di tipi Sum , ed è ancora chiaramente una generalizzazione del Sequenza di Fibonacci, ma che valuta anche efficientemente in ghci? Dove comincio?

E mi chiedo se simili insidie attendono anche nel codice compilato tramite ghc -O2 . E se sì, come si comportano gli autori del codice Haskell con quelli?

Un'altra domanda correlata è Quando è il momento giusto per ragionare sulle prestazioni in Haskell? . Penso che la mia domanda sia ancora più fondamentale; Non capisco nemmeno come fare il compito di tale ragionamento. C'è una risposta ragionevole in questo caso, ma non ho abbastanza informazioni specifiche per farmi effettivamente scrivere un fibSums_list che funziona in ghci , per non parlare di uno che ha una sorta di complessità temporale garantita.

haskell

posta Weston Markham 08.01.2018 - 00:29

fonte

1 risposta

Leggi altre domande sui tag haskell

Iniezione delle dipendenze vs Livelli di miscelazione dell'astrazione Come impedire ad altri utenti di utilizzare variabili non thread-safe in un ambiente multithreading?

score 3 · Answer 1

Nessuna risposta può fornire esaustivamente il vero modo di ragionare sulla complessità algoritmica di Haskell. In parte questo è dovuto al fatto che un sacco di codice Haskell si basa su ciò che il compilatore effettivamente farà in pratica (GHC può rendere un programma più veloce o più lento di quanto ci si aspetterebbe). Ma io posso spiegare la fonte della tua sorpresa nell'esempio che hai dato, e forse ti guiderà ad alcune illuminazioni su come Haskell valuta le cose.

For example, we also use polymorphism to express functions in a generic fashion, again without sacrificing clarity. However, when combined with lazily-evaluated structures, the two language features seem to interact in ways that are (to me) surprising.

Se controlli il Core IR per il codice che hai scritto per fibSums_list , verranno rivelate alcune cose:

fibSums_list :: forall a. Sum a => [a]
fibSums_list
  = \ (@ a) ($dSum :: Sum a) ->
      : (one $dSum)
        (: (one $dSum)
           (zipWith
              (add $dSum) (fibSums_list $dSum) (tail (fibSums_list $dSum))))

fibSums_list viene abbassato a una funzione, non un valore!
Un valore che descrive Sum a è in realtà un parametro della funzione.
Quando scrivi fibSums_list nel corpo, in realtà stai chiamando la funzione in modo ricorsivo con l'argomento implicito.

Tying this back to the language, qualsiasi "valore" polimorfico deve essere ben tipizzato da solo. Pertanto, il significato di fibSums_list è "dammi un thunk attraverso il quale posso calcolare questo valore nell'ambiente di classe specificato". Un po 'di tempo per elaborare questo articolo dovrebbe convincerti che condividere il thunk non è strettamente necessario per ottenere un risultato corretto quando si esce da un indice.

Quindi un modo migliore di pensare a funzioni polimorfiche ad-hoc potrebbe essere quello di considerarle come fabbriche OOP per costruire i loro valori reali da un ambiente di classe di tipografia. Con questo in mente, puoi ottenere la lista infinita che desideri:

fibSums_list :: Sum a => [a]
fibSums_list = fibz
  where fibz = one : one : zipWith add fibz (tail fibz)

Ora, quando guardiamo al Core, possiamo vedere chiaramente il comportamento di "fabbrica".

fibSums_list :: forall a. Sum a => [a]
fibSums_list
  = \ (@ a) ($dSum :: Sum a) ->
      letrec {
        fibz :: [a]
        fibz
          = break<3>()
            : (one $dSum)
              (break<2>()
               : (one $dSum)
                 (break<1>() zipWith (add $dSum) fibz (break<0>() tail fibz))); } in
      break<4>(fibz) fibz

Il valore fibz esiste all'interno di fibSums_list , quindi l'ambiente di classe è già stato stabilito. Ciò significa che fibz non è una funzione, ma un valore con un thunk coerente che verrà espanso pigramente.

Puoi vedere questo in action computing fibS 100 in GHCI qui .

Sospetto che il motivo per cui GHC's -O2 sta producendo codice veloce per te è perché è specializzato fibSums_list e lo riscrive in modo che l'ambiente di classe sia corretto dal punto di vista di fibS . Quindi diventa come se avessi scritto fibSums_list :: [Integer] e tutto diventa molto più semplice.