(Zainspirowany moją odpowiedzią na to pytanie ).
Rozważ ten kod (powinien znaleźć największy element, który jest mniejszy lub równy podanemu wejściu):
data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)
closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing where
precise :: Maybe (Integer, v) -> TreeMap v -> Maybe (Integer, v)
precise closestSoFar Leaf = closestSoFar
precise closestSoFar (Node k v l r) = case i `compare` k of
LT -> precise closestSoFar l
EQ -> Just (k, v)
GT -> precise (Just (k, v)) r
To nie jest zbyt leniwe. Po GT
wpisaniu sprawy wiemy na pewno, że końcowa wartość zwrotna będzie Just
czymś, a nie Nothing
, ale Just
nadal nie będzie dostępna do końca. Chciałbym uczynić to bardziej leniwym, aby Just
było dostępne od razu po wpisaniu GT
sprawy. Mój przypadek testowy polega na tym, że chcę Data.Maybe.isJust $ closestLess 5 (Node 3 () Leaf undefined)
ocenić True
raczej niż dno. Oto jeden ze sposobów, w jaki mogę to zrobić:
data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)
closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess _ Leaf = Nothing
closestLess i (Node k v l r) = case i `compare` k of
LT -> closestLess i l
EQ -> Just (k, v)
GT -> Just (precise (k, v) r)
where
precise :: (Integer, v) -> TreeMap v -> (Integer, v)
precise closestSoFar Leaf = closestSoFar
precise closestSoFar (Node k v l r) = case i `compare` k of
LT -> precise closestSoFar l
EQ -> (k, v)
GT -> precise (k, v) r
Jednak teraz powtarzam: podstawowa logika jest teraz zarówno w, jak closestLess
i wewnątrz precise
. Jak mogę to napisać, żeby było leniwe, ale nie powtarzałem się?
źródło
Zaczynając od mojej niezbyt leniwej implementacji, najpierw zmieniłem zdanie
precise
na otrzymaneJust
jako argument i odpowiednio uogólniłem jego typ:Potem zmieniłem to na
wrap
wczesne i nazwałemid
wGT
przypadku:To nadal działa dokładnie tak jak poprzednio, z wyjątkiem korzyści dodatkowego lenistwa.
źródło
id
pośrodku pomiędzyJust
i finałem są(k,v)
eliminowane przez kompilator? prawdopodobnie nie, funkcje powinny być nieprzejrzyste, afirst (1+)
zamiast tego można by użyć (typowo wykonanego) zamiastid
do wszystkich kompilatorów, jakie zna. ale tworzy zwarty kod ... oczywiście, mój kod jest tutaj twoją eksploracją i specyfikacją, z dodatkowym uproszczeniem (eliminacjąid
s). również bardzo interesujące, jak bardziej ogólny typ służy jako ograniczenie, relacja między zaangażowanymi wartościami (choć nie wystarczająco ścisła, zfirst (1+)
dopuszczeniem jakowrap
).precise
jest używany w dwóch typach, bezpośrednio odpowiadających dwóm specjalistycznym funkcjom stosowanym w bardziej szczegółowym wariancie. niezła gra. Ponadto nie nazwałbym tego CPS,wrap
nie jest używany jako kontynuacja, nie jest wbudowany „wewnątrz”, jest ułożony - przez rekurencję - na zewnątrz. Może gdyby był użyty jako kontynuacja, moglibyście pozbyć się tych obcychid
... btw ponownie możemy zobaczyć tutaj ten stary wzorzec argumentu funkcjonalnego wykorzystanego jako wskaźnik tego, co robić, przełączając się między dwoma kierunkami działania (Just
lubid
).Myślę, że wersja CPS, na którą sam odpowiedziałeś, jest najlepsza, ale dla kompletności oto kilka innych pomysłów. (EDYCJA: Odpowiedź Buhra jest teraz najbardziej wydajna.)
Pierwszym pomysłem jest pozbyć się
closestSoFar
akumulatora „ ”, a zamiast tego pozwolićGT
skrzynce obsłużyć całą logikę wyboru najmniejszej wartości prawej od argumentu. W tej formieGT
sprawa może bezpośrednio zwrócićJust
:Jest to prostsze, ale zajmuje dużo miejsca na stosie, gdy trafisz wiele
GT
skrzynek. Technicznie można by tego użyć nawetfromMaybe
w postaci akumulatora (tj. ZastępującfromJust
ukrytą odpowiedź Luquiego), ale byłaby to zbędna, nieosiągalna gałąź.Drugi pomysł, że tak naprawdę są dwie „fazy” algorytmu, jedna przed i jedna po naciśnięciu a
GT
, więc parametryzujesz go wartością logiczną, aby reprezentować te dwie fazy, i używasz typów zależnych do kodowania niezmiennika, że zawsze będzie wynik w drugiej fazie.źródło
Co powiesz na
?
źródło
Just
ale jest całkowity. Wiem, że twoje rozwiązanie w formie pisemnej jest w rzeczywistości całkowite, ale jest kruche, ponieważ pozornie bezpieczna modyfikacja mogłaby wówczas doprowadzić do dna.Just
tak będzie, dlatego doda test, aby upewnić się, że nie zaNothing
każdym razem będzie się powtarzał.Nie tylko zawsze wiemy
Just
, że po pierwszym odkryciu zawsze wiemyNothing
do tego czasu . To właściwie dwie różne „logiki”.Więc idź w lewo przede wszystkim, dlatego , że wyraźne:
Cena jest taka, że powtarzamy co najwyżej jeden krok maksymalnie raz.
źródło