중첩 된 요소 목록을 평면화하는 기능이 있습니까?

중첩 된 요소 목록을 평면화하는 기능이 있습니까?

---

다음과 같이 중첩 된 목록을 어떻게 병합 할 수 있습니까?

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

---

아무도 이것을주지 않았기 때문에 MultiParamTypeClasses를 사용하여 임의의 깊이의 목록을 평탄화하는 함수를 정의하는 것이 가능합니다. 실제로 유용하다고 생각하지는 않았지만 흥미로운 해킹으로 간주 될 수 있기를 바랍니다. Oleg의 다변량 함수 구현에서 아이디어를 얻었습니다.

{-# 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

---

예,의 concat, 표준의 전주곡에서 주어진

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

당신이 설정하고 싶은 경우 [[[a]]]에 [a], 당신은 그것을 두 번 사용해야합니다 :

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

---

다른 사람들이 지적했듯이 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

---

import Data.List
let flatten = intercalate []

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

---

hammar가 지적했듯이, join목록을 병합하는 "모나 딕"방법입니다. do-Notation을 사용하여 여러 수준의 함수를 쉽게 병합 할 수 있습니다.

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

---

임의로 중첩 된 목록은으로 근사화 Data.Tree할 수 있으며 적절하게 명명 된 함수로 평면화 할 수 있습니다 flatten.

I say approximated because Data.Tree allows a data item to be attached to every node, not just the leaves. However, you could create a Data.Tree (Maybe a), and attach Nothing to the body nodes, and flatten with catMaybes . flatten.

---

You can remove one level of nesting using concat, and consequently you can apply n levels of nesting by applying concat n times.

It is not possible to write a function which removes an arbitrary level of nestings, as it is not possible to express the type of a function, which takes an arbitrarily nested list and returns a flat list, using Haskell's type system (using the list datatype that is - you can write your own datatype for arbitrarily nested lists and write a flatten function for that).

ReferenceURL : https://stackoverflow.com/questions/5994051/is-there-a-function-to-flatten-a-nested-list-of-elements