Sto cercando di ottimizzare il codice:altezza minima in tree
data Tree = Empty | Node Integer Tree Tree
minHeight Empty = -1
minHeight (Node _ Empty Empty) = 0
minHeight (Node _ l r ) = (min (minHeight l) (minHeight r)) + 1
Il mio obiettivo è quello di non calcolare i rami la cui profondità sarà superiore a quello già noto.
È possibile utilizzare Peano Nat s invece di Integer s e lasciare che la pigrizia fare il lavoro:
data Nat = S Nat | Z deriving (Eq)
instance Ord Nat where
min (S n) (S m) = S (min n m)
min _ _ = Z
instance Enum Nat where
fromEnum Z = 0
fromEnum (S n) = fromEnum n + 1
data Tree = Empty | Node Integer Tree Tree
minHeight Empty = Z
minHeight (Node _ l r) = S (min (minHeight l) (minHeight r))
tree = Node 0 (Node 1 tree Empty) tree
main = print $ fromEnum $ minHeight tree -- 2
Molto bello. Si noti che il calcolo di 'min' richiede direttamente meno codice rispetto al confronto:' minNat (S m) (S n) = S (minNat m n); minNat _ _ = Z'. – dfeuer
quindi fondamentalmente questa soluzione si basa sul fatto che ad es. '1 <= 1 + abs someComputation' dovrebbe essere in grado di essere valutato a' True' senza valutare 'someComputation', ma che è possibile solo se invece di' 1' e '3', è stata usata una rappresentazione migliore di naturals rispetto a 'Int' /' Integer' - molto bello! –
@dfeuer, inoltre 'minNat n Z' è' Z', mentre 'min n Z' (dove' min' è definito tramite '(<=)') non calcola. Quindi la mia versione non funziona per 'tree = Node 0 tree (Node 1 tree Empty)', mentre i tuoi lavori. Grazie per il suggerimento. – user3237465
Si desidera contare la profondità dall'alto e utilizzare i valori restituiti di minHeight per rilegare le altre chiamate.
minHeight :: Integer -> (Maybe Integer) -> Tree -> Integer
minHeight depth bound tree = ...
passano inizialmente in 0 come profondità e Nothing come legato (aka Infinity), le foglie tornare il più piccolo dei depth e bound, altrimenti vedere se si dispone di un insieme finito legato (Just b) e confrontarlo con corrente depth.
case b of
Just min -> if min <= depth then return min else RECURSION
otherwise -> RECURSION
Ogni volta che sei al computer alcune minHeight in ricorsione, unire il suo risultato con la corrente bound.
minHeight d min (Node _ t1 t2) =
let min1 = Just (minHeight (d + 1) min t1) in
(minHeight (d + 1) min1 t2)
Ecco una soluzione, che non calcola i rami, la cui profondità sarà superiore alla già noto uno:
data Tree = Empty | Node Integer Tree Tree
minHeight :: Tree -> Int
minHeight =
loop Nothing 0
where
loop defaultDepth depth tree =
case defaultDepth of
Just x | x <= depth ->
x
_ ->
case tree of
Empty -> depth
Node _ left right ->
loop (Just (loop defaultDepth (succ depth) left)) (succ depth) right
Nota: indipendentemente dalla convenzione utilizzata, se si desidera essere coerenti, 'Empty' e' Node _ Empty Empty' non dovrebbero avere la stessa altezza. – Jubobs
@Jubobs si, modificato! –
Puoi modificare nella domanda cosa intendi per lunghezza_lunga e lunghezza corrente? – Franky