Понимание функции Хаскеля с помощью лямбда-исчисления - PullRequest
Новая
       62

Понимание функции Хаскеля с помощью лямбда-исчисления

0 голосов
/ 25 декабря 2018

Я пытаюсь определить функцию фильтра.Основываясь на определении функции, функция фильтра - это функция (скажем, функция справки, отличная от функции основного фильтра), которая принимает функцию и список для получения списка.Функция help принимает переменную и возвращает значение Bool.Но в соответствии со строкой 4, функция справки вычисляет наряду с [x] значение Bool, которое затем возвращает список.

Итак, я могу понять функцию справки как функцию, которая принимает a и [a] для получения значения Bool.Функция основного фильтра затем принимает значение Bool, чтобы вернуть список?

Я знаю, что определение функции не предполагает этого, но это довольно логично, основываясь на коде.Спасибо 

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' a (x:xs)
  | a x == True = x:filter' a xs
  | otherwise = filter' a xs

Ответы [ 2 ]

0 голосов
/ 26 декабря 2018

Вы можете использовать синтаксис еще больше, чтобы помочь вашему пониманию: 

filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs)
     | (p  x) == True   = x : ( filter' p xs )
     | otherwise        =     ( filter' p xs )

То есть 

filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs)
     | (p  x)     = x : ( filter' p xs )
     | otherwise  =     ( filter' p xs )

Или перевести его на более простые конструкции, 

filter' :: (a -> Bool) 
          ->   [a] -> [a]
filter' p = ( \ xs -> case xs of 
             {  []            ->  []
             ;  (x:ys) | p x  ->  x : ( filter' p ys )
             ;  (x:ys)        ->      ( filter' p ys )  } )

"p" для "предиката" .Он используется filter' для проверки каждого x на входе xs, чтобы решить, включать ли этот x или нет в выходной файл, в соответствии со значением Bool ean, которое произвело тестирование.

p просто передается без изменений от одного вызова filter' к следующему.Это обычно закодировано с помощью так называемого преобразования «рабочий-обертка», 

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = go xs where
   go [] = []
   go (x:xs) | p x   = x : go xs
             | otherwise = go xs

Наконец, более простое определение может также быть 

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = go xs where
   go []     = []
   go (x:xs) = [x | p x] ++ go xs

, которое хорошо соответствует *Определение на основе 1030 * 

filter' p = foldMap (\ x -> [x | p x])
0 голосов
/ 26 декабря 2018

Я думаю, это будет понятнее, если мы дадим функции типа a -> Bool имя, отличное от a. 

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' f (x:xs)
  | f x == True = x:filter' f xs
  | otherwise = filter' f xs

Теперь f имеет тип a -> Bool, x :: a,и xs :: [a].

Мне нравится ваше описание (a -> Bool) -> [a] -> [a] как «принимает функцию и список, чтобы дать список».Рекурсивные вызовы filter' в строках 4 и 5 имеют одинаковый тип.f передается без изменений.xs - это список a с, но он на a короче, чем список ввода.Существует только одна функция filter'.Определение функции относится к самому себе - это важная часть того, что мы подразумеваем под «рекурсивной функцией».

...