Блог

Я пишу функцию для фильтрации первого заданного значения из списка в Haskell.

Я опробовал функцию, основанную на функции filter, но я не знаю, как выполнялась функция.

Поэтому я добавляю трассировку к каждому случаю.

 filter' :: (a -> Bool) -> [a] -> [a]
filter' p (x:xs) | p x       = trace "{1}" x : (filter' p xs)
                 | otherwise = trace "{2}" filter' p xs
filter' p [] = []


filterFirst :: (a->Bool) -> [a]->[a]
filterFirst p xs = case (trace "{3}" (filter' p xs)) of 
  (x : xs) -> trace "{4}" [x]
  otherwise -> trace "{5}" []
  

при тестировании:

filterFirst even [2,2] оказывается

 {3}
{4}
[{1}
2]
  

filterFirst even [1,2] оказывается

 {3}
{2}
{4}
[{1}
2]
  

filterFirst even [1,1,2] оказывается

 {3}
{2}
{2}
{4}
[{1}
2]
  

Результат [2] правильный, но последовательность выполнения является проводной.

1. Почему {4} выполняется раньше {1}?
2. {3}, похоже, выполняется только один раз, почему case of знает, когда тестировать (x : xs) ?
3. Как case of выполняется точно?

 trace "{1}" x : (filter' p xs)
  

разбирается как

 (trace "{1}" x) : (filter' p xs)
  

Аналогично,

 trace "{2}" filter' p xs
  

разбирается как

 (trace "{2}" filter') p xs
  

Если вы хотите другую интерпретацию, вам нужно написать trace "{1}" (x : (filter' p xs)) и trace "{2}" (filter' p xs) соответственно.

Я не уверен в вашем вопросе № 3. Зачем {3} выполнять несколько раз? Это не часть цикла / рекурсии.

Давайте пройдемся по оценке

 filterFirst even [2,2]
  

Интерпретатор хочет напечатать результат, поэтому мы должны вычислить результат.

Мы вводим определение filterFirst (внешняя часть выражения всегда вычисляется первой), выдавая

 case (trace "{3}" (filter' p xs)) of 
  (x : xs) -> trace "{4}" [x]
  otherwise -> trace "{5}" []

where
    p = even
    xs = [2,2]
  

Здесь нам нужно принять решение. case необходимо знать, какую ветвь оценивать, поэтому ему нужно знать, какой шаблон соответствует ( x : xs или otherwise ). Итак, первое, что он делает, это оценивает выражение, которое мы анализируем:

 trace "{3}" (filter' p xs)

where
    p = even
    xs = [2,2]
  

Здесь самым внешним выражением является вызов trace , который теперь печатается {3} и передается

 filter' p xs

where
    p = even
    xs = [2,2]
  

Теперь самым внешним выражением является вызов filter' , который определяется как

 filter' p (x:xs) | p x       = trace "{1}" x : (filter' p xs)
                 | otherwise = trace "{2}" filter' p xs
filter' p [] = []
  

И снова мы должны принять решение: какое уравнение мы используем? Выбор зависит от значения второго аргумента, поэтому это запускает вычисление (самого внешнего уровня) xs = [2,2] . Ну, здесь ничего интересного не происходит, потому что [2,2] уже полностью оценена.

[2,2] является синтаксическим сахаром для 2 : (2 : []) , так что это соответствует первому уравнению, связывающему

 p = even
x = 2
xs = 2 : []  -- same as [2]
  

Теперь нам нужно оценить защиту, стоящую за шаблоном:

 p x
even 2
True
  

Успех! Нашим возвращаемым значением является trace "{1}" x : (filter' p xs) , которое (как упоминалось выше) является применением (:) к двум аргументам, trace "{1}" x и filter' p xs .

Дальнейшая оценка здесь не выполняется. Напомним, что мы все еще пытаемся оценить

 case ... of 
  (x : xs) -> trace "{4}" [x]
  otherwise -> trace "{5}" []
  

итак, нас волнует только, является ли самый внешний конструктор списка : или [] , и мы знаем, что это : сейчас. Мы выбираем первую ветвь, которая выдает

 trace "{4}" [x]

where
    x = trace "{1}" x_inner
    xs = filter' p xs_inner
    x_inner = 2
    xs_inner = 2 : []
    p = even
  

Это немного сбивает с толку, потому что вы назвали все свои переменные x и xs . Если мы встроим все переменные, значения которых мы уже знаем, привязки уменьшатся до:

 trace "{4}" [x]

where
    x = trace "{1}" 2
    xs = filter' even (2 : [])
  

xs не используется вообще и x используется только один раз, так что это действительно эквивалентно

 trace "{4}" [trace "{1}" 2]
  

Оценка этого сначала выводит {4} (из trace ), затем выдает

 [trace "{1}" 2]
-- syntactic sugar for
(trace "{1}" 2) : []
  

Здесь начинает работать код печати списка: у нас есть список, состоящий по крайней мере из одного элемента, поэтому он выводит [ (начало списка). Чтобы напечатать сам первый элемент, нам нужно его оценить:

 trace "{1}" 2
  

Это, наконец, печатает {1} и выдает 2 результат, который позволяет выводить код для печати списка 2 и ] (для конца списка).

И это все!

Я не все проверил, но обратите внимание, что

 trace "{1}" x : (filter' p xs)
  

означает

 (trace "{1}" x) : (filter' p xs)
  

таким образом, {1} будет напечатано при доступе к содержимому первого элемента, а не при его простом создании. Я думаю, вы хотели

 trace "{1}" (x : (filter' p xs))
  

Я бы также переписал {2} строку как

 trace "{2}" (filter' p xs)