W funkcjonalnie w Haskell (P 213), jesteśmy pokazani dwie wersje cyklicznej listy. Jeden ocenia się w czasie kwadratowym:

iterate3 f x = x:map f (iterate3 f x)

iterate3 (2*) 1
= 1:map (2*) (iterate3 (2*) 1)
= 1:2:map (2*) (map (2*) (iterate3 (2*) 1))
= 1:2:4:map (2*) (map (2*) (map (2*) (iterate3 (2*) 1)))

Drugi, który używa where, ocenia się w czasie liniowy:

iterate2 f x = xs where xs = x:map f xs

iterate2 (2*) 1    
xs          where xs = 1:map (2*) xs
= 1:ys      where ys = map (2*) (1:ys)
= 1:2:zs    where zs = map (2*) (2:zs)
= 1:2:4:ts  where ts = map (2*) (4:ts)

Nie do końca rozumiem tej oceny. W jaki sposób X przypisuje się do każdego kolejnego elementu listy zamiast 1 (jak w pierwszej wersji)?

3
planarian 17 luty 2017, 06:33

2 odpowiedzi

Najlepsza odpowiedź

Ważnym szczegółem jest to, że xs w iterate2 jest zdefiniowany pod względem samego siebie, tworząc strukturę kołową.
(To czasami nazywa się "wiązaniem węzła".)

Wizualizacja go jako wykresu ocena ma coś w ten sposób (ostrzeżenie: Art ASCII).

xs where xs = 1 : map (2*) xs:

     :  <----------+
   /   \           | applies to
  1    map (2*)  --+

-->

     :
   /   \
  1     :  <--------+   
      /   \         | applies to
     2   map (2*) --+

-->

     :
   /   \
  1     : 
      /   \
     2     : <---------+
         /   \         | applies to
        4   map (2*) --+

I tak dalej.

4
molbdnilo 17 luty 2017, 12:31

Rozwińmy rekurencję w iterate2:

xs = x : map f xs
   = x : map f (x : map f xs)                          -- Inline xs
   = x : (f x) : map f (map f xs)                      -- Definition of map
   = x : (f x) : map f (map f (x : map f xs))          -- Inline xs
   = x : (f x) : map f ((f x) : map f (map f xs))      -- Definition of map
   = x : (f x) : (f (f x)) : map f (map f (map f xs))) -- Definition of map
   ...

Widać więc, że lista zwrócona przez iterate2 f x ma x jako pierwszy element, f x jako drugi i tak dalej.

1
Cactus 17 luty 2017, 03:37