Creating a data type list Haskell

Question

I've done a personal list in Haskell like this: (2,(1,1),3) -> List [Num 2, List [Num 1, Num 1], List [Num 3]].

This is how I made it:

data SList a = Num a | List [SList a] deriving Show
emptySList :: SList a
emptySList = (List [])

consElem :: a -> SList a -> SList a
consElem x (List y) = (List ((Num x) : y))

consList :: SList a -> SList a -> SList a
consList a b = (List [a,b])

I manage to form this list (List [Num 2, List [Num 1, Num 1], List [Num 3]]) using consElem and consList like this:

consElem 2 $ consList (consElem 1 $ consElem 1 emptySList) $ consElem 3 emptySList

I wonder how can I transform a SList in a normal list. For example if I have this SList: List [Num 2, List [Num 1, Num 1], List [Num 3]] it should become [2,1,1,3].

My attempt:

atomToNormal x
    | null x = []
    | otherwise = slistToList (head x) ++ atomToNormal (tail x)
slistToList :: SList a -> [a]
slistToList (List x) = atomToNormal x
slistToList (Num x) = [x]

What have you tried so far? (Your SList is a tree type, so any tree traversal should work.) — melpomene
– melpomene, Commented Apr 17, 2017 at 11:00
This is what I have by now : onebyone (Num x) = x atomToNormal x | null x = [] | otherwise = (onebyone $ head x) : atomToNormal (tail x) slistToList (List x) = atomToNormal x — JoeDonald
– JoeDonald, Commented Apr 17, 2017 at 11:01
That looks like it would almost work. You just have to change (onebyone $ head x) : to slistToList (head x) ++ (and handle the Num case in slistToList). — melpomene
– melpomene, Commented Apr 17, 2017 at 11:05
I change the code as you said. But it doesn't work. It bring me this error: No instance for (Num (SList [t0])) — JoeDonald
– JoeDonald, Commented Apr 17, 2017 at 11:14
So put slistToList :: SList a -> [a] in your code and see if you get a better error message. :-) — melpomene
– melpomene, Commented Apr 17, 2017 at 11:23

leftaroundabout · Accepted Answer · 2017-04-17 11:28:47Z

1

GHC can actually write this function for you:

{-# LANGUAGE DeriveFoldable #-}
import Data.Foldable as Foldable

data SList a = Num a | List [SList a]
  deriving (Show, Foldable)

slistToList :: SList a -> [a]
slistToList = Foldable.toList

If you want to do it yourself – I don't see quite what atomToNormal is supposed to do, you don't need it. Just deconstruct the tree-branch list^† head-first right in slistToList:

slistToList :: SList a -> [a]
slistToList (Num x) = _
slistToList (List []) = _
slistToList (List (l:ls)) = _

Now fill in the gaps. GHC (>=7.10) can help you a lot there too: just try compiling as-is with the underscore-gaps, and it will tell you

/tmp/wtmpf-file17703.hs:8:23:
    Found hole ‘_’ with type: [a]
    Where: ‘a’ is a rigid type variable bound by
               the type signature for slistToList :: SList a -> [a]
               at /tmp/wtmpf-file17703.hs:7:16
    Relevant bindings include
      x :: a (bound at /tmp/wtmpf-file17703.hs:8:18)
      slistToList :: SList a -> [a]
        (bound at /tmp/wtmpf-file17703.hs:8:1)
    In the expression: _
    In an equation for ‘slistToList’: slistToList (Num x) = _

So the first gap needs to have type [a], and the only value you have is x::a. Well, you can wrap that in a singleton list

slistToList (Num x) = [x]

Proceed in the same fashion with the other clauses. As a rule of thumb, if you just somehow include all of the “relevant bindings” (often, there's exactly one way to do this), then your implementation will probably be right.

Of course, this only works when you first write out the type signature... which should always be the first thing you do anyway!

^†_{Your type really should be called something tree-ish, not SList!}

edited Apr 17, 2017 at 11:28

answered Apr 17, 2017 at 11:19

leftaroundabout

121k6 gold badges185 silver badges337 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Lazersmoke Over a year ago

This type is actually Free [] a, and I would use it as such. Something called Tree a is relatively ambiguous about its meaning, while Free [] a is very standard. Best to use a type synonym or newtype + GND for instances.

leftaroundabout Over a year ago

@Lazersmoke well, it is also the standard Tree type from the containers package. I would use it by that name. Sure, like many other types you can also express it through Free, but what's the point? If you'd go this route consequently, you'd actually have to write Free (Free (Free (Const ()))). This is silly.

Lazersmoke Over a year ago

@leftaroundabout Tree is Cofree []. SList Char can be List [List [Num 'a']], Free [] Char can be Free [Free [Pure 'a']], Cofree/Tree can't do this.

leftaroundabout Over a year ago

Alright, true. In particular you can have (even arbitrarily deep) empty structures with Free [], whereas Tree always has at least one value. Actually rather a forest than a tree thus.

Collectives™ on Stack Overflow

Creating a data type list Haskell

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related