Haskell последовательность выполнения

Question

кто-нибудь может помочь мне понять этот код

solve s | s == 0 = Nothing 
     | s == 1 = Just 1 
     | otherwise = 
      check [solve (s-(x*2)) | x <- [1..9]] 

check x = case x of 
      []   -> Nothing 
      (Nothing:xs) -> check xs 
      (x:xs)  -> x  

почему это дает стек над потоком, когда я попытался запустить его с четным значением, и есть ли способ в Haskell, где я могу отладить и увидеть фактическое значение текущей программы, как в eclipse мы делаем?

спасибо

Answer 1

По крайней мере, с GHCi, нет никакого способа, чтобы «шаг» с помощью кода (Edit: больше не верно, см комментарии ниже), но вы можете, конечно, добавить отладочные с помощью Debug.Trace. Другими словами, если вы хотите, чтобы проверить все рекурсивные вызовы solve вы можете сказать:

check [trace ("solving for " ++ show (s-(x*2)))) (solve (s-(x*2))) | x <- [1..9]] 

Есть чистые пути, чтобы написать, что, но это просто иллюстрирует идею.

В этом конкретном случае причина, по которой она бесконечно повторяется, состоит в том, что базовые случаи решения никогда не будут достигнуты. solve 2, например, решает check [solve 0, solve -2, solve -4 ..., solve -16] и solve -2 решает check [solve -4, solve -6, ...] т.д.

Answer 2

Переполнение стека предлагает бесконечную рекурсию. Ветвление в противном случае «решайте» не может быть завершено. Я не уверен, что этот код должен делать здесь, поэтому я не могу предложить исправление. Надеюсь, это поможет!

Answer 3

solve s | s == 0 = Nothing 
     | s == 1 = Just 1 
     | otherwise = 
      check [solve (s-(x*2)) | x <- [1..9]] 

В случае solve 2:

(2 - (1 * 2)) = 0 (0 - (2 * 2)) = -2

и так далее.

Я не уверен насчет отладочного материала, но именно поэтому он переполняет стек. Это бесконечно рекурсивно.

Answer 4

Добавляя к ответу Дэн, вы можете просто нажать на след там в решении, и это покажет проблему.

solve s | s == 0 = Nothing 
     | s == 1 = Just 1 
     | otherwise = 
      trace (show s) $ check [solve (s-(x*2)) | x <- [1..9]] 

Answer 5

Вы можете переписать, что первые части, используя шаблон, соответствующий вместо этого, это намного приятнее нотации, чем охранники (если-заявление);)

solve 0 = Nothing 
solve 1 = Just 1 
solve s = check [solve (s - (x * 2)) | x <- [1..9]] 

Список постижение покормить диапазон от 1 до 9 в решаем метод, который вызывает решение с s - (x * 2) и, честно говоря, я не могу интуитивно сказать, что это закончится ... но давайте рассмотрим некоторые примеры.

solve 2 

Вызов решения 2 приведет в следующем списке, так как Haskell ленив, что список не будет иметь значения, пока вы (не имеют побочных эффектов) попытаться напечатать эти ...

solve s - 1 * 2 
solve s - 2 * 2 
solve s - 3 * 2 
solve s - 4 * 2 
solve s - 5 * 2 
solve s - 6 * 2 
solve s - 7 * 2 
solve s - 8 * 2 
solve s - 9 * 2 

Простой solve 2 попробует solve -2, который попытается решить другие проблемы, и это не закончится.

Answer 6

check :: [Maybe a] -> Maybe a 
check = Data.Maybe.listToMaybe . Data.Maybe.catMaybes 

solve :: (Num a, Num b) => a -> Maybe b 
solve 0 = Nothing 
solve 1 = Just 1 
solve s = solve (s-2) 

здесь, это довольно очевидно, что solve -1 и solve 5.3 будет работать бесконечно. эта версия решения будет работать точно так же, как цикл while. оригинальная версия, которую вы отправили, будет спама в каждом вызове ненужных вещей в ваш ram/stack.

можно переписать так:

solve s = check [solve (s-x)|x<-[2,4..18]] 

к этому:

solve s = check [solve (s-2),solve (s-4),solve (s-6),solve (s-8),solve (s-10),solve (s-12),solve (s-14),solve (s-16),solve (s-18)] 

но когда solve (s-2) возвращает Nothing, то каждый solve (s-x) будет возвращать, потому что значение было уже опробовали как это: solve ((((s-2)-2)-2)-2)

Это экспоненциальный алгоритм для проверки sth, который может быть проверен линейным временем или рассчитан в c постоянное время.

я предлагаю прочитать эту книгу: Haskell: The Craft of Functional Programming