Есть ли функция сглаживания вложенного списка элементов?

Ответ 1

Поскольку никто не дал этого, можно определить функцию, которая будет сглаживать списки произвольной глубины с помощью MultiParamTypeClasses. Я на самом деле не нашел его полезным, но, надеюсь, его можно было бы считать интересным взломом. Я получил идею от реализации поливарианской функции Олега.

{-# LANGUAGE MultiParamTypeClasses, OverlappingInstances, FlexibleInstances #-}

module Flatten where

class Flatten i o where
  flatten :: [i] -> [o]

instance Flatten a a where
  flatten = id

instance Flatten i o => Flatten [i] o where 
  flatten = concatMap flatten

Теперь, если вы загрузите его и запустите в ghci:

*Flatten> let g = [1..5]
*Flatten> flatten g :: [Integer]
[1,2,3,4,5]
*Flatten> let h = [[1,2,3],[4,5]]
*Flatten> flatten h :: [Integer]
[1,2,3,4,5]
*Flatten> let i = [[[1,2],[3]],[],[[4,5],[6]]]
*Flatten> :t i
i :: [[[Integer]]]
*Flatten> flatten i :: [Integer]
[1,2,3,4,5,6]

Обратите внимание, что обычно необходимо предоставить аннотацию типа результата, так как иначе ghc не может определить, где остановить рекурсивно применение метода класса flatten. Если вы используете функцию с мономорфным типом, которая, однако, достаточно.

*Flatten> :t sum
sum :: Num a => [a] -> a
*Flatten> sum $ flatten g

<interactive>:1:7:
    No instance for (Flatten Integer a0)
      arising from a use of `flatten'
    Possible fix: add an instance declaration for (Flatten Integer a0)
    In the second argument of `($)', namely `flatten g'
    In the expression: sum $ flatten g
    In an equation for `it': it = sum $ flatten g
*Flatten> let sumInt = sum :: [Integer] -> Integer
*Flatten> sumInt $ flatten g
15
*Flatten> sumInt $ flatten h
15

Ответ 2

Да, его concat из стандартной прелюдии, заданный

concat :: [[a]] -> [a]
concat xss = foldr (++) [] xss

Если вы хотите превратить [[[a]]] в [a], вы должны использовать его дважды:

Prelude> (concat . concat) [[[1,2],[3]],[[4]]]
[1,2,3,4]

Ответ 3

Как указывали другие, concat :: [[a]] -> [a] - это функция, которую вы ищете, и она не может сгладить вложенные списки произвольной глубины. Вы должны вызвать его несколько раз, чтобы сгладить его до желаемого уровня.

Однако операция выполняет обобщение на другие монады. Затем он известен как join и имеет тип Monad m => m (m a) -> m a.

Prelude Control.Monad> join [[1, 2], [3, 4]]
[1,2,3,4]    
Prelude Control.Monad> join (Just (Just 3))
Just 3
Prelude Control.Monad.Reader> join (+) 21
42

Ответ 4

Как указывал хаммар, join является "монадическим" способом сгладить список. Вы можете использовать do -Notation, чтобы писать легко сглаженные функции нескольких уровней:

flatten xsss = do xss <- xsss
                  xs <- xss
                  x <- xs
                  return x

Ответ 5

import Data.List
let flatten = intercalate []

flatten $ flatten [[[1,2],[3]],[[4]]]
[1,2,3,4]

Ответ 6

Скользящий список может быть аппроксимирован символом Data.Tree, который может быть сплющен соответствующей функцией flatten.

Я говорю приблизительно, потому что Data.Tree позволяет прикреплять элемент данных к каждому node, а не только к листам. Однако вы можете создать Data.Tree (Maybe a) и прикрепить Nothing к узлам тела и сгладить с помощью catMaybes . flatten.

Ответ 7

Вы можете удалить один уровень вложенности с помощью concat, и, следовательно, вы можете применить n уровней вложенности, применяя concat n раз.

Невозможно написать функцию, которая удаляет произвольный уровень вложений, поскольку невозможно выразить тип функции, которая принимает произвольно вложенный список и возвращает плоский список, используя систему типа Haskell (используя тип данных списка - вы можете написать свой собственный тип данных для произвольно вложенных списков и написать для него функцию сглаживания).