Свести случайным образом вложенный список в не вложенный список с помощью Haskell - PullRequest
Новая
       33

Свести случайным образом вложенный список в не вложенный список с помощью Haskell

0 голосов
/ 30 октября 2018

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

a ::(Num a, Num [a], Num [[a]]) => [[a]]
a = [1, 2, [3, 4]]

b :: (Num a, Num [a], Num [[a]], Num [[[a]]]) => [[[[a]]]]
b = [[1,2,[3]],4]

Функция, которую я пытаюсь создать, должна делать следующее: 

myFunc a == [1,2,3,4]
myFunc b == [1,2,3,4]

Первоначально я думал, что мне придется проанализировать список в AST (абстрактное синтаксическое дерево) --> использовать рекурсию, чтобы сгладить все ветви и уйти в одну ветку --> проанализировать результат обратно в список.

Я не уверен, как разобрать список в AST? или есть лучшее решение?

edit - я думаю, что я пытался быть слишком буквальным, потому что представление [1, 2, [3, 4]] на самом деле является частью проблемы, поэтому для того, чтобы вещи работали лучше, их нужно было бы представить в виде ADT / AST. Итак, если бы это был ответ API или чтение файла, как бы я проанализировал эти данные в AST / ADT?

Ответы [ 3 ]

0 голосов
/ 30 октября 2018

Непонятно, чего вы на самом деле пытаетесь достичь, но есть синтаксический взлом, который на самом деле позволяет написать синтаксис списка с вложенным списком в Haskell и автоматически сгладить его: 

{-# LANGUAGE TypeFamilies #-}

import GHC.Exts (IsList(..))

newtype AutoflatList a = AutoflatList {getFlatList :: [a]}
   deriving (Show)

instance IsList (AutoflatList a) where
  type Item (AutoflatList a) = AutoflatList a
  fromList segs = AutoflatList $ getFlatList =<< segs
  toList = pure

instance Num a => Num (AutoflatList a) where
  fromInteger = AutoflatList . pure . fromInteger

*Main> :set <a href="https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html?highlight=overloadedlists#extension-OverloadedLists" rel="nofollow noreferrer">-XOverloadedLists</a>
*Main> [1, 2, [3, 4]] :: AutoflatList Int
AutoflatList {getFlatList = [1,2,3,4]}
*Main> [[1,2,[3]],4] :: AutoflatList Int
AutoflatList {getFlatList = [1,2,3,4]}

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

0 голосов
/ 30 октября 2018

Это уже сделано для вас GHC. Сплющивание складное. 

> :set -XDeriveFoldable

> data NList a = A a | N [NList a] deriving (Show, Functor, Foldable)
data NList a = A a | N [NList a]

> foldMap pure (N[ A 1, N[ A 2], A 3]) :: [Int]
[1,2,3]

> foldMap pure (N[ N[ N[ N[ A 1]]], N[ A 2], A 3]) :: [Int]
[1,2,3]
0 голосов
/ 30 октября 2018

Произвольно вложенный список не проверяет тип. Каждый элемент списка должен иметь одинаковый тип, но списки с разными уровнями вложенности имеют разные типы. Хитрость заключается в том, чтобы обернуть список в новый тип данных, который скрывает количество вложенных уровней. Но это всего лишь дерево. 

data Tree a = Root a | Branches [Tree a]

Тогда вы можете реализовать flatten как обход дерева. 

flatten :: Tree a -> [a]
flatten (Root a)          = [a]
flatten (Branches (t:ts)) = flatten t ++ (concat (fmap flatten ts))

См. Data.Tree в упаковке контейнера для готовой к использованию версии.

Для разбора я бы порекомендовал использовать aeson. Data.Aeson.Types определяет экземпляр FromJSON v => FromJSON (Tree v), поэтому вы должны просто иметь возможность использовать decode в строке json и сказать, что хотите Tree Int. 

decode rawJson :: Maybe (Tree Int)
...