CODEWITHSUNDEEP
haskell
eliasgander
eliasgander

Reputation: 165

Create a list through nested pairs

I'm working on an university assignment and the the task involves building a list in the form of nested pairs. For the pairs there exists a datastructure like: 

data Data = Pair { first :: Data, second :: Data } | ...

I tried to write an append function that takes a pair and the new value which is appended to the given pair: 

append :: Pair ->     Data ->     Pair
append    p           new         = append' p p new
where
    append' ::   Pair ->         Pair ->                    Data ->         Pair
    append'      p               cur@(Pair Nil _)           new             = p where { cur = cur { first=new } }
    append'      p               cur@(Pair _ Nil)           new             = p where { cur = cur { second=(Pair new Nil) } }
    append'      p               cur@(Pair _ (Pair _ _))    new             = append' p (second cur) new

The idea was to always keep a reference to the given pair that is returned at the end (p) and at the same time move (cur) recursively through the nested Pair structure until the end is encountered (second is Nil) at which then the new element is added in form of another pair.
I assume this doesn't work because it requires pass by reference which is not the case in side-effect-less Haskell.
I'd be very grateful if anybody could point me in the right direction on how to solve this problem.

Upvotes: 0

Views: 152

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

Haskell conceptually has not really references. Sure Haskell uses a lot of references (to reduce for instance the memory load), and there are modules like Data.IORef where we can use references by using IO. But such functions do not really have conceptual references.

Furthermore you use something like p where {cur = cur {first = new } }, which seems like you look for an assignment. Haskell has no assignments, it only has declarations.

In case you want to append, you thus need to construct a new Pair. We can for instance use:

append :: Pair -> Data -> Pair
append (Pair Nil r) dat = Pair dat r
append (Pair l Nil) dat = Pair l dat
append (Pair l r) dat = Pair l (append r dat)

So for the first two lines, we construct a new pair where we replace the Nil by data. In the latter case (both are non-Nil), we construct a new pair, where we make a recursive append call to calculate the new right part.

Upvotes: 4

Related Questions