Iterating (mapping) tipo di dati ricorsivo in Haskell

Question

Iterating (mapping) tipo di dati ricorsivo in Haskell

#1 da (2 voti)
#2 da (2 voti)
#3 da (2 voti)

3

Questa potrebbe essere una domanda stupida, ma visto che non ho nessuno con cui discutere per un caffè, penso che lo chiederei qui. Quindi, sto leggendo il libro "The Haskell School of Expression" per imparare un po 'di Haskell e hanno il seguente tipo:

data Picture = Region Color Region
         | Picture 'Over' Picture
         | EmptyPic
deriving Show

In seguito, quando devono convertire un'immagine in un elenco di regioni, lo fanno in modo ricorsivo in questo modo:

picToList EmptyPic = []
picToList (Region c r) = [(c, r)]
picToList (p1 'Over' p2) = picToList p1 ++ picToList p2

Questo è tutto buono e piuttosto facile, ma quello che mi ha fatto pensare è che dovevano farlo manualmente. Haskell è pieno di astrazioni, quindi mi chiedo, ha un'astrazione per iterare su tipi di dati ricorsivi? Dopotutto, il compilatore conosce la struttura del tipo di dati e internamente probabilmente rappresenta i dati sotto forma di un grafico di qualche tipo, quindi può attraversarlo per me in un modo generico? Non ho idea di come funzionerebbe nella pratica, ma Haskell è abbastanza diverso da tutti gli altri linguaggi di programmazione che conosco, quindi forse c'è un concetto che non riesco nemmeno a immaginare.

haskell

posta Leonid 08.03.2016 - 13:46

fonte

3 risposte

Leggi altre domande sui tag haskell

Gestione degli errori di basso livello Il modello di strategia non è sufficiente per il mio problema?

score 2 · Answer 1

L'attraversamento non è banale. Mentre sembra che tu abbia un albero semplice, non deve essere così. Facciamo solo un'iterazione sulle foglie o facciamo pre-ordine o attraversamento post-ordine? Se abbiamo un grafico piuttosto che un albero, come gestiamo gli elementi duplicati? Questa è la risposta migliore a chiunque stia implementando quella struttura dati, non dal compilatore.

score 2 · Answer 2

A seconda di cosa esattamente vuoi fare, c'è:

Data.Functor
Data.Foldable
Data.Traversable

Functor ti permette di mappare sulla tua struttura, pieghevole, ovviamente permette una piega e attraversa una mappa e piega. Ora non l'ho usato da solo ma sembrano esserci dei modi per portare il compilatore a automaticamente ricava istanze per questi typeclass per te (non ho idea se questo è possibile nel caso tu dia comunque)

Un paio di cose da notare qui sono:

Questo introduce sia i typeclass che la magia per scriverli automaticamente, quindi potrebbe facilmente essere un motivo per lasciarli fuori dal tutorial in un libro se questi argomenti non sono stati introdotti.

Inoltre, naturalmente, la maggior parte delle lingue imperative dovresti programmare in modo esplicito un attraversamento su qualsiasi nuova struttura in qualsiasi modo, quindi questa potrebbe non essere una funzione che la lettura si aspetta sia disponibile.

score 2 · Answer 3

Questo non risponde direttamente alla tua domanda, ma c'è un typeclass Foldable che include la funzione toList :: Foldable t => t a -> [a] . Inoltre, GHC è in grado di derivarne delle istanze, come nel seguente codice banalmente semplice:

{-# LANGUAGE DeriveFoldable #-}

data Foo a = Foo a (Foo a)
           | Bar
             deriving (Show, Foldable)

Usalo in GHCi:

GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> :load derive-foldable.hs
[1 of 1] Compiling Main             ( derive-foldable.hs, interpreted )
Ok, modules loaded: Main.
*Main> import qualified Data.Foldable as F
*Main F> let f = Foo 1 (Foo 2 (Foo 3 Bar))
*Main F> F.toList f
[1,2,3]

Questo non si applica nel tuo caso, non ultimo perché (in termini di base, imprecisi) il tuo tipo Picture non ha un parametro. Tuttavia, è davvero un'astrazione per iterare su tipi di dati ricorsivi. Questa derivazione automatica di un'istanza Foldable è tuttavia più magica di GHC e meno essenziale di Haskell.