Lazy generation of pairs of adjacent elements in a "circular list"

Question

To check for ray-triangle collisions, we can first see if the ray collides with the triangle's plane. If it does, we then check if the intersection point is on the same side for all triangle sides. If true, this means that the point is inside the triangle. This procedure is analogous for rectangles and other convex figures.

This is a list of vertexes belonging to a rectangle (counter-clockwise ordered):

vertexes = [ll, lr, ur, ul]

and I want to generate a list with all its sides; that is, all adjacent pairs of vertexes:

vertexPairs = [(ll, lr), (lr, ur), (ur, ul), (ul, ll)]

(note that the last vertex, ul, also pairs with the first one, ll)

How can I lazily generate such a list for a generic convex geometric figure, assuming I have an ordered list of its vertexes?

---

The idea is to feed each of the pairs to a function, isInside, and check if all of its return values are the same. This is what I'm doing:

1.  vertexes = [<list of vertexes>]
2.  vertexPairs = ???
3.  results = map (\(v1, v2) -> isInside point v1 v2) vertexPairs
4.  allequal = all (== head results) (tail results)

Because Haskell is lazy, if a call to isInside returns a value that differs from the first call's return value, the call to all ends (line 4). Similarly, I wanted a way to generate the vertexPairs list in a lazy way.

---

As I was writing this question, I thought of a possible solution to generate the pairs:

vertexPairs = zip (vertexes) (tail vertexes ++ [head vertexes])

1. Is this lazy? I would say so, as it doesn't use last or similar functions, but I'm still relatively new to Haskell.
2. It also looks a bit ugly, thanks to the concatenation and single-element list. Is there a better way?
3. As a related question, what should be the free-point notation for line 3?

Answer 1

Yes this way of generating the list is lazy. In general, list functions in Haskell are lazy.

You can test whether it's lazy yourself by including something that will error out (e.g. undefined) in the initial list. For example, if

vertexes = [(0,0), (10,0), undefined, undefined]

then vertexPairs will give you an error (since it needs to evaluate the whole list to print it). However, if it's lazy, head vertexPairs should still give you the correct pair--and it does!

I think your code actually looks rather good. The tail vertexes ++ [head vertex] makes what you're doing very clear. Yes, it looks a little odd to use ++ here, but it makes sense: appending to the end of the list is an expensive operation, so it should stand out. I can't think of any better way to write that code. As a minor style hint, you can drop the parentheses around vertexes:

vertexPairs = zip vertexes (tail vertexes ++ [head vertexes])

For 3., conceptually, you want to apply isInside point to each pair. Right now it has a type like Point -> Point -> Bool. You want to get a function that takes its first two arguments as a tuple: (Point, Point) -> Bool. This function is called uncurry because the opposite transformation (turning a function that expects a tuple into one of multiple parameters) is called currying. So you could write 3. like this:

results = map (uncurry (isInside point)) vertexPairs

Answer 2

Though tikhon has answered most questions, if you want to write it in a slightly prettier way, you could do

vertexPairs v = zip v (tail $ cycle v)

This works since zip stops generating a list when one of its arguments "run out"