Конкатенация в Haskell и путаница с AList ([a] -> [a]) - PullRequest
Новая
       68

Конкатенация в Haskell и путаница с AList ([a] -> [a])

1 голос
/ 17 февраля 2020

У меня есть проект, в котором мы улучшаем скорость объединения списка в Haskell. Я новичок в Haskell и запутался в AList ([a] -> [a]) В частности, как преобразовать мой AppendedList в обычный список. Любая помощь будет оценена. 

newtype AppendedList a = AList ([a] -> [a])

-- List[5] is represented as AList (\x -> 5:x) 
-- This function takes an argument and returns the AppendedList for that 
single :: a -> AppendedList a
single m = AList (\x -> m : x)


-- converts AppendedList to regular List
toList :: AppendedList a -> [a]
toList = ???

Ответы [ 2 ]

6 голосов
/ 18 февраля 2020

Самое сложное - не дать вам ответ напрямую:)

Если вы помните, как списки строятся в Haskell: [1, 2, 3] = 1 : 2 : 3 : [], где [] является пустым списком .

Теперь давайте «следуем за типами» (мы также называем этот мыслительный процесс TDD для разработки на основе типов) и посмотрим, что у вас под рукой: 

toList :: AppendedList a -> [a]
toList (AList listFunction) = ???

и listFunction имеет тип [a] -> [a]. Поэтому вам нужно предоставить ему список полиморфных c (то есть список любого типа ), чтобы он возвращал вам список.

Что является единственным списком любой тип вы знаете? Передайте этот список на listFunction, и все скомпилируется, что является хорошим показателем того, что это, вероятно, правильно: D

Надеюсь, это поможет без предоставления простого ответа (цель - научиться!).

0 голосов
/ 18 февраля 2020

AppendedList a это тип.

AList f - это тип данных с некоторой функцией f :: [a] -> [a] "внутри него".

f - это функция от списков к спискам с элементами одного типа.

Мы можем назвать это с some_list :: [a], чтобы получить resulting_list :: [a]: 

f           :: [a] -> [a]
  some_list :: [a]
-------------------------
f some_list ::        [a]

resulting_list ::     [a]
resulting_list = f some_list

Мы можем использовать resulting_list в качестве some_list тоже, т.е. 

resulting_list = f resulting_list

, потому что он имеет тот же тип, который соответствует ожиданиям f (и из-за лени Haskell). Таким образом, 

toList (...) = let { ... = ... } 
               in ...

является одним из возможных определений. При этом 

take 2 (toList (single 5))

вернет [5,5].

edit: Конечно [5,5] не является списком, содержащим single 5. Более того, take 4 ... вернет [5,5,5,5], поэтому наше представление содержит любое количество пятерок, а не только одну из них. Но он содержит только одно отдельное число, 5.

Это напоминает два экземпляра Applicative Functor для списков, [] и ZipList. pure 5 :: [] Int действительно содержит только одну пятерку, но pure 5 :: ZipList Int содержит любое количество пятерок, но только пятерок. Конечно, сложно добавлять бесконечные списки, так что в основном это просто любопытство. Пища для размышлений.

В любом случае это показывает, что есть не просто один способ написать код, который проверяет здесь тип. В нашем распоряжении больше, чем один список. Самый простой из них - это действительно [], а другой ... сам наш список!

...