Почему этот тип не проверяет?

compress xs@(_:_:_) = (ifte <$> ((==) <$> head <*> head.tail) <$> ((compress.).(:) <$> head <*> tail.tail) <*> ((:) <$> head <*> compress.tail) ) xs

В результате возникает ошибка типа, но я не понимаю, почему. Это должно быть эквивалентно

compress xs@(_:_:_) = (ifte (((==) <$> head <*> head.tail) xs) (((compress.).(:) <$> head <*> tail.tail) xs) (((:) <$> head <*> compress.tail) xs))

, что не так.

примечание: ifte = (\ x y z -> if x then y else z) , <$> и <*> взяты из Control.Applicative .

EDIT: ошибка:

Couldn't match expected type `[a]' with actual type `[a] -> [a]'
    In the expression:
        (ifte <$> ((==) <$> head <*> head . tail)
     <$>
       ((compress .) . (:) <$> head <*> tail . tail)
   <*>
     ((:) <$> head <*> compress . tail))
      $ xs
    In an equation for `compress':
        compress xs@(_ : _ : _)
          = (ifte <$> ((==) <$> head <*> head . tail)
         <$>
           ((compress .) . (:) <$> head <*> tail . tail)
       <*>
         ((:) <$> head <*> compress . tail))
          $ xs

Я столкнулся с этой проблемой, пытаясь написать бесточечное решение проблемы 8 из Девяносто девять задач Haskell< /а>. Я пытался сделать это, изменив точечное решение, которое я написал, которое было

compress::Eq a => [a]->[a]
compress [] = []
compress (x:[]) = (x:[])
compress (x:y:xs) = ifte ((==) x y) (compress (x:xs)) (x:(compress (y:xs)))

debugging types typechecking haskell pointfree
person aaa    schedule 22.10.2011    source источник
comment
Не могли бы вы вставить ошибку типа и, возможно, менее точную версию кода?   -  person fuz    schedule 23.10.2011
comment
Извиняюсь. Вы даете нам большую кучу бессмысленного и непрозрачного кода для расшифровки, даже не упоминая цель кода или какие-либо подробности, такие как точная ошибка, которую вы получаете. Как мы должны вам помочь? -1.   -  person fuz    schedule 23.10.2011
comment
-1. Это типичная ситуация, когда вы пьете стакан воды и думаете, что, черт возьми, вы делаете на самом деле.   -  person Tarrasch    schedule 23.10.2011
comment
Я думаю, что OP экспериментировал с pointfree (что обычно дает такой аппликативный беспорядок) и пытался избавиться от if-then-else с помощью ifte.   -  person sdcvvc    schedule 23.10.2011

Ответы (3)


arrow_upward
6
arrow_downward

Во-первых, отступ. Во-вторых, рассмотрите возможность использования некоторых переменных.

Даже при более разумном форматировании видно, что это

compress =
  ifte <$> ((==) <$> head <*> head.tail)
       <$> ((compress.).(:) <$> head <*> tail.tail)
       <*> ((:) <$> head <*> compress.tail)

когда это должно быть

compress =
  ifte <$> ((==) <$> head <*> head.tail)
       <*> ((compress.).(:) <$> head <*> tail.tail)
       <*> ((:) <$> head <*> compress.tail)

В-третьих, даже если вы должны быть непостижимы, как насчет

compress (x:r@(y:_)) = ifte (x==y) id (x:) $ compress r

или, точка бесплатно

compress = map fst . filter (uncurry (/=)) . (zip <$> id <*> tail)
person Brandon    schedule 22.10.2011
comment
или даже compress = map head . group - person sdcvvc; 23.10.2011
comment
Также ваш последний безточечный код удаляет последний элемент списка, возможно, это не то, что хотел ОП. - person sdcvvc; 23.10.2011
comment
Это другое? В исходном коде отсутствует базовый вариант для конечных списков, поэтому я не беспокоился о хвостах. - person Brandon; 23.10.2011
comment
Брэндон: Базовый случай для конечных списков можно легко добавить с дополнительными уравнениями для пустых и одноэлементных списков (на самом деле OP добавил их, о чем идет речь), но последнюю версию не так просто изменить. - person sdcvvc; 23.10.2011

arrow_upward
5
arrow_downward

Вот ваш код, написанный немного более читабельно

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative

u = ((==) <$> head <*> head.tail)
v = ((compress.).(:) <$> head <*> tail.tail)
w = ((:) <$> head <*> compress.tail)

ifte = (\ x y z -> if x then y else z) 

--compress xs@(_:_:_) = (ifte <$> u <$> v <*> w) xs
compress xs@(_:_:_) = (ifte (u xs) (v xs) (w xs))

Надеюсь, теперь вы видите ошибку - правильная версия

--compress xs@(_:_:_) = (ifte <$> u <*> v <*> w) xs
person sdcvvc    schedule 22.10.2011
comment
+1 за то, что взял ужасный вопрос и сделал из него что-то полезное - person Daniel Wagner; 23.10.2011

arrow_upward
2
arrow_downward

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

import Control.Applicative

ifte :: Bool -> a -> a -> a
ifte b t f = if b then t else f

compress :: Eq a => [a] -> [a]
-- compress = ifte <$> cond <$> t <*> f
-- We will leave compress undefined so we can load this into ghci.
-- After some trial and error it is clear that this is the part
-- that doesn't type check
compress = undefined

cond :: Eq a => [a] -> Bool
cond = (==) <$> head <*> head . tail

t :: Eq a => [a] -> [a]
t = (compress .) . (:) <$> head <*> tail . tail

f :: Eq a => [a] -> [a]
f = (:) <$> head <*> compress . tail

Здесь я разделил его, и, как упомянул Брэндон, на этом этапе вы должны увидеть, что ошибка заключается в использовании <$> вместо <*>. Вы освоитесь с этой концепцией, продолжая изучать аппликативный стиль, где ваши выражения обычно имеют один <$>, за которым следует произвольный # из <*>:

f <$> a <*> b <*> c <*> d <*> ...

Тем не менее, игнорируя это понимание, я временно присвоил каждому подвыражению тип и TLD. Это позволяет мне загрузить файл в ghci и немного поэкспериментировать.

ghci> :t ifte <$> cond <$> t <*> f
... Eq a => [a] -> [a] -> [a]

ВТФ??? Это типа звук??? Оно должно было выдать ошибку, но, видимо, с этим выражением все в порядке. Или это? Обратите внимание, что сигнатура этого типа не совпадает с той, которую мы хотим для compress.

ghci> :t compress
... Eq a => [a] -> [a]

Подвыражения соответствуют сигнатурам типов, которые мы от них ожидаем, о чем свидетельствует то, что компилятор нас не тошнит. Поскольку это так, проблема явно заключается в том, как мы их комбинируем. Итак, какие части мы хотим объединить здесь? Игнорирование ограничений Eq:

ifte :: Bool -> [a] -> [a] -> [a]
cond :: [a] -> Bool
t    :: [a] -> [a]
f    :: [a] -> [a]

-- desired result
     :: [a] -> [a]

Здесь я сделал тривиальную специализацию ifte для [a] вместо любого a. Связь ясна: тип вывода cond, t и f соответствует типу ввода ifte. Нам просто нужно передать всем трем этим выражениям одно и то же [a]. Признавая, что (input ->) является аппликативным, мы обобщаем:

arg1 :: (a -> b -> c -> d)
arg2 :: f a
arg3 :: f b
arg4 :: f c
res  :: f d

-- for our case,
-- f = ([a] ->)
-- a = Bool
-- b = [a]
-- c = [a]
-- d = [a]

Стоп... Время погуглить! Выбирая (a -> b -> c -> d) -> f a -> f b -> f c -> f d, мы сразу находим liftA3, что не удивительно:

liftA3 f a b c = f <$> a <*> b <*> c
person Dan Burton    schedule 22.10.2011