flatten a nested list Classic List Threaded 7 messages Open this post in threaded view
|

flatten a nested list

 I would like to write a program that can do something like this.   ;; lisp syntax * (my-flatten '(1 (2 (3 4) 5))) (1 2 3 4 5) I end up like this. data Store a = E a | S [Store a]              deriving (Show) flat :: [Store a] -> [a] flat [] = [] flat ((E x):xs) = [x] ++ flat xs flat ((S x):xs) = flat x ++ flat xs so *Main> flat [E 1, S[E 2, S[E 3, E 4], E 5]] [1,2,3,4,5] Compare to a Lisp solution, It 's not looking good. Any suggestion. Thanks, PPhetra
Open this post in threaded view
|

Re: flatten a nested list

 pphetra: > > I would like to write a program that can do something like this. >   > ;; lisp syntax > * (my-flatten '(1 (2 (3 4) 5))) > (1 2 3 4 5) > > I end up like this. > > data Store a = E a | S [Store a] >              deriving (Show) > > flat :: [Store a] -> [a] > flat [] = [] > flat ((E x):xs) = [x] ++ flat xs > flat ((S x):xs) = flat x ++ flat xs > > so > *Main> flat [E 1, S[E 2, S[E 3, E 4], E 5]] > [1,2,3,4,5] > > Compare to a Lisp solution, It 's not looking good. > Any suggestion. Since this data type: > data Store a = E a | S [Store a] >              deriving (Show) Is isomorphic to the normal Data.Tree type anyway, so we'll use that: > data Tree a = N a [Tree a] >   deriving Show to define a new tree: > tree = N 1 [N 2 [N 3 [], N 4 []], N 5 []] Now we can flatten by folding: > flatten t = go t [] >   where go (N x ts) xs = x : foldr go xs ts So we can flatten our test tree: > list = flatten tree Even run it: > main = print (flatten tree) Or in GHCi: *Main> flatten tree [1,2,3,4,5] Based on Data.Tree in the base library. -- Don _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: flatten a nested list

 On Fri, Dec 29, 2006 at 07:58:54PM +1100, Donald Bruce Stewart wrote: > Since this data type: > > > data Store a = E a | S [Store a] > >              deriving (Show) > > Is isomorphic to the normal Data.Tree type anyway, so we'll use that: It's a bit different - store has labels only in its leaves. Best regards Tomasz _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: flatten a nested list

 In reply to this post by pphetra On Thu, Dec 28, 2006 at 11:56:58PM -0800, pphetra wrote: > data Store a = E a | S [Store a] >              deriving (Show) > > flat :: [Store a] -> [a] > flat [] = [] > flat ((E x):xs) = [x] ++ flat xs > flat ((S x):xs) = flat x ++ flat xs > > so > *Main> flat [E 1, S[E 2, S[E 3, E 4], E 5]] > [1,2,3,4,5] Since this problem is fundimentally tied to Lisp's dynamic typing, it is no suprise it can be done very easily using Haskell's support for dynamic typing: > import Data.Typeable > data D = forall a. Typeable a => D a  deriving(Typeable) > flat :: D -> [D] > flat (D x) = maybe [D x] (>>= flat) (cast x) To use: map (\ (D x) -> cast x) flat (D [D 1, D [D 2, D 3], D 4]) :: [Maybe Integer] The 'D' defines an existantial type, which can hold a value of any type subject to the Typeable constraint. Typeable allows the typesafe cast function, which returns Nothing if the types were different. maybe and >>= are prelude functions used to make the definition shorter; without them: > flat (D x) = case (cast x) of Just xs -> concatMap flat xs >                               Nothing -> [D x] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|