Блог

Главная - Вопросы по программированию - Почему это вычисление с фиксированной точкой не прекращается?

Почему это вычисление с фиксированной точкой не прекращается?

#haskell #infinite-loop #lazy-evaluation #fixpoint-combinators #infinite-recursion

Вопрос:

Я новичок в Haskell, и у меня есть следующий код:

 second (x:y:xs) = y : second xs  -- returns every second element of a list
second _ = []

xs = [1,2,3,4]    second xs

Я ожидаю xs , что меня оценят [1,2,3,4,2,4,4] , потому что это фиксированная точка, [1,2,3,4,2,4,4] == [1,2,3,4] second [1,2,3,4,2,4,4] т. Е.

Однако, когда я пытаюсь оценить xs в GHCi, я получаю

 Prelude> xs
[1,2,3,4,2,4,4

но это не останавливает вычисления.

Может ли кто-нибудь объяснить, почему это не прекращается, и есть ли простой способ остановить и вернуть вычисления [1,2,3,4,2,4,4] ?

Ответ №1:

[1,2,3,4,2,4,4] [] является фиксированной точкой ([1,2,3,4] ) . second , но это не наименее фиксированная точка.

То есть [1,2,3,4,2,4,4] undefined то , что меньше. Он меньше в том смысле, что он менее определен, чем первый.

Первый из них более определен тем, что у него определен его 7-й хвост, в то время как у второго 7-й хвост undefined .

Таков общий прогноз. Но конкретно мы можем следовать вычислениям шаг за шагом, называя все промежуточные значения и расширяя определение, и мы обнаружим, что точка «получить» в результате догоняет точку «положить», которая изначально находится дальше, но точка «получить» в два раза быстрее, чем «положить». Так что, когда они встретятся, там еще не будет ничего, что мы туда положили, что мы могли бы получить.

Таким образом, вычисление застревает, ожидая, что что-то появится там, где ничего нет, и нет ничего, что могло бы что-то туда поместить.

Единственный способ избежать этого- take 7 надеть его сверху.

На несвязанной ноте я бы назвал эту функцию seconds , нет second .

Итак, все происходит так:

 xs = [1,2,3,4]    second xs

              a b c         (_:a:p) = xs = [1,2,3,4]  second xs
              ↓ ↓ ↓         (_:b:q) = p  = [    3,4,2]  second p
   =  1 2 3 4 2 4 4         (_:c:r) = q  = [        2,4]  second q
        ↓   ↓   ↓   ↓                 r  = [            4]  second r
        a   b   c    
      ↑   ↑   ↑   ↑                  r = drop 2 q = second q = 
      xs  p   q   r                    = second (2:4:r) = 4:second r

head r четко определено, это

 r = drop 2 q = second q 
             = second (_:c:r) 
             = c:second r
head r = c = 4
tail r =

но тогда нам нужно найти tail r . Это (:) узел передачи данных? Так ли это [] ?

        = tail (c:second r)
       = second r               -- (1)
       = second (c:second r)
       = case (c:second r) of
           (x:y:z) -> y:second z
           []      -> []
       = case (second r) of     -- (2)
           (y:z) -> y:second z

и поэтому, чтобы выяснить, что second r такое ( (1) ), нам нужно выяснить, что second r такое ( (2) ).

Мы застряли.

Комментарии:

1. Небольшая демонстрация gist.github.com/pedrofurla/ffc61559d7a4fba74d4c42c6da0c3832 Я собирался добавить что-то к ответу, но для полноты его нужно было бы оценить все вручную. Это было бы утомительно.

2. take 7 это не единственный выбор. Вы также можете определить свой собственный оператор точки фиксации, который работает путем повторного применения и проверки на равенство, например fixEq :: Eq a => (a -> a) -> (a -> a); fixEq f guess | guess' == guess = guess | otherwise = fixEq f guess' where guess' = f guess .

3. @WillNess Вызовет его с любым (конечным, полностью определенным) списком guess , например fixEq (([1,2,3,4] ) . second) [] , как .

4. @eivour Err… да! Моя математика не работает в обоих моих последних комментариях. Вот исправленное: текущая реализация-O(n*log(n)). Алгоритм Брента имеет ту же асимптотическую сложность (но, вероятно, в любом случае быстрее). Ни один универсальный алгоритм с фиксированной точкой не может работать асимптотически лучше. Специализированный алгоритм (а не универсальный) может привести вас к O(n).

5. @WillNess Нравится fix , fixEq только обещает вернуть точку исправления, и не обязательно ту точку исправления, которую вы имеете в виду .

Ответ №2:

Еще один более интуитивный способ увидеть это заключается в том, что [] (конец списка) должен откуда-то взяться. second Функция вернется [] только после того, как она встретит a [] на входе, так что в итоге вы столкнетесь с ситуацией с курицей и яйцом. В этом случае [] он никогда не создается, и поэтому вычисление никогда не может прекратиться.

Комментарии:

1. second возвращает [] всякий раз, когда в списке меньше двух элементов, поэтому повторное применение second в конечном итоге возвращает [] .

2. Не совсем , например xs = [] second xs .

3. @eivour Для того, чтобы вход имел менее двух входов , он уже должен иметь a [] , так как даже одноэлементный список [x] фактически x:[] находится за кулисами. И это [] должно откуда-то исходить-аргумент » second производит [] , потому что видит [] , что пришло second » приводит к вопросу «но почему [] пришло second «… бесконечный регресс. [] Чтобы исходить откуда-то из конечного аргумента, он должен исходить из чего-то другого, чем рекурсивный вызов second .

4. @eivour … и, чтобы быть откровенным, в то время как Хаскелл прекрасно выполняет бесконечные значения , он вообще не использует бесконечные аргументы (здесь я использую «аргументы» в смысле моего предыдущего комментария, а не в смысле «аргументов функций»).

5. @DanielWagner выясняет, что виновником здесь является r = 4:second r последняя «ячейка минусов». Я отредактировал свой ответ с учетом особенностей. 🙂

Метки: