CODEWITHSUNDEEP
haskell
user15553
user15553

Reputation: 301

Referring to previous term in a list in Haskell

There's something I'd like to be able to do in Haskell, but it's not obvious if it's possible. I'm a novice (for instance, I don't yet understand monads), so maybe there is some advanced way of doing it.

Suppose I have defined a function f from some type to itself. I would like to be able to define a notion "prev" that would stand for the previous element in a list (of elements of the given type). So I would like something like [x, y, f prev] to mean [x, y, f y]. I don't mind if the definition involves zipping the list with the natural numbers, as long as what I get to write in the end can hide the method of construction.

One reason this may be impossible is that if it is possible, then one ought also to be able to define a notion of "next", and one wouldn't want to be able to write [f next, g prev]. If it is impossible, is there a next best option?

Upvotes: 2

Views: 1458

Answers (2)

chi
chi

Reputation: 116139

You can define your own knot-tying combinators to obtain something like

example :: [Int]
example = tie [ const 1, succ . prev, succ . prev, (*2) . next, const 100, const 20 ]
-- yields     [       1,           2,           3,         200,       100,       20 ]

Intuitively, const value means that value is the element of the list. Instead, operation . prev means that this element is obtained applying operation to the previous element. The expression operation . next works similarly.

Further, you can refer to both previous and next using uncurry e..g.

example2 :: [Int]
example2 = tie [ const 100, uncurry (+), const 5 ]
-- yields      [       100,         105,       5 ]

A possible implementation is

tie :: [ (a,a) -> a ] -> [a]
tie = go (error "no previous element")
  where go _  []     = []
        go pr (f:fs) = this : rest
            where rest = go this fs
                  this = f (pr, head rest)

prev :: (a,a) -> a
prev = fst

next :: (a,a) -> a
next = snd

Live demo

Upvotes: 2

Ganesh Sittampalam
Ganesh Sittampalam

Reputation: 29100

I don't think there's a way to introduce a new keyword prev to get the exact syntax you describe, at least short of some techniques that would be significant overkill for this scenario, like implicit parameters or Template Haskell.

However you can do this using a technique called tying the recursive knot:

type PrevList a = [a -> a]

instantiatePrevList :: PrevList a -> [a]
instantiatePrevList prevList =
    let result =
           zipWith (\f prev -> f prev)
                   prevList
                   (error "Initial element has no previous element":result)
    in result

xs = instantiatePrevList [\_ -> 5, \_ -> 3, \prev -> prev + 1]

The idea is to define your list in terms of functions that are always passed the previous value - the PrevList type above. You can then choose to ignore it if you don't need it for a particular element.

We then need a function to put it all together which is what instantiatePrevList does.

Notice that the list result is defined in terms of itself, which is where the "tying the knot" comes in - it relies on Haskell's laziness to work.

The other way laziness is used is for the first element, which has no previous. As long as you don't try to use the previous value in the first element of your list, the error won't be hit.

As you surmise, the same technique could also be used to define a next - and it would still work fine as long as you don't write something that is actually dependent on itself in a non-terminating way.

EDIT:

Actually a solution with implicit parameters isn't too complicated and it does make for nicer syntax writing the lists:

{-# LANGUAGE ImplicitParams, ImpredicativeTypes, ScopedTypeVariables #-}

type PrevList a = [(?prev :: a) => a]

instantiatePrevList :: PrevList a -> [a]
instantiatePrevList prevList =
    let result =
           zipWith (\(elem :: ((?prev :: a) => a)) prev ->
                             let ?prev = prev in elem)
                   prevList
                   (error "Initial element has no previous element":result)
    in result

xs = instantiatePrevList [5, 3, ?prev + 1]

You do have to be a bit careful with them though, you might get confusing results if you try to nest them - e.g. by having a PrevList within another PrevList.

Upvotes: 5

Related Questions