# Does it make sense to have a Range data type?

**URL:** <https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826>\
**Category:** Learn\
**Created:** [February 18, 2024, 7:20pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826 "2024-02-18T19:20:16Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 18, 2024, 7:20pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/1 "2024-02-18T19:20:16Z")

</div>

A common pattern is `for_` of a list enumeration, like

```haskell
for_ [0 :: Int .. 4] $ \i ->
  print i
-- 0
-- 1
-- 2
-- 3
-- 4

```

The pattern works well but it doesn’t really express what we want. We don’t care to actually make a list; we just want to iterate over the increasing sequence of numbers. In practice GHC probably optimizes all this away to something much nicer, but it’s risky to rely on it: if `[0 .. 1000 * 1000]` occurs twice in our program then GHC may float it to the top level and materialise it. That’s a space leak!

Maybe we should have a `Range` type instead? For example, see below. I’m actually surprised I’ve never seen anything like this before. Of course, it can be adjusted to incorporate different step sizes too (including negative step sizes). What do folks think of it?

```haskell
import Data.Foldable

data Range a where
  MkRange :: (Enum a, Ord a) => !a -> !a -> Range a

instance Foldable Range where
  foldMap f (MkRange i j) =
    if i > j
    then mempty
    else f i <> foldMap f (MkRange (succ i) j)

example =
  for_ (MkRange @Int 0 4) $ \i ->
    print i

-- ghci> example
-- 0
-- 1
-- 2
-- 3
-- 4

```

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 18, 2024, 8:10pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/2 "2024-02-18T20:10:02Z")

</div>

This range data type is a special case of the Stream type used in stream fusion, e.g.:

[https://hackage.haskell.org/package/stream-fusion-0.1.2.5/docs/src/Data-Stream.html#Stream](https://hackage.haskell.org/package/stream-fusion-0.1.2.5/docs/src/Data-Stream.html#Stream)

The obvious advantage of lists is that its one less data type to keep in mind and learn about.

I think the best way to avoid the leak is just to teach GHC not to float out in these cases. And I think GHC already does not do that.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 18, 2024, 8:25pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/3 "2024-02-18T20:25:32Z")

</div>

I suspect `Stream` is slower in practice, at least, that’s what seemed to be the conclusion of [some investigation into fighting undesirable sharing in the `streaming` library](https://github.com/haskell-streaming/streaming/issues/110#issue-1035177418) (where a different, but similar, data type is also called `Stream`).

> The obvious advantage of lists is that its one less data type to keep in mind and learn about.

Yes, I suppose so.

> I think the best way to avoid the leak is just to teach GHC not to float out in these cases. And I think GHC already does not do that.

Could be. But sometimes maybe you _do_ want to float lists out, when you _expect_ them to be fully materialized. How would GHC distinguish those cases? In any case, it’s quite hard to default `-ffull-laziness`.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 18, 2024, 9:49pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/4 "2024-02-18T21:49:09Z")

</div>

The streaming package (and `conduit` and `pipes`) uses a fundamentally different structure which indeed has the same problems as lists. They basically use a normal nested ADT, but the `Stream` I pointed to is a combination of a strict state and a step function. That step function prevents sharing.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 18, 2024, 9:56pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/5 "2024-02-18T21:56:15Z")

</div>

Sure, but the discussion I linked shows that putting the next result behind a function call introduces an appreciable slowdown.

---

<div class="post-metadata">

**Author:** ![Vlix](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/vlix/32/1551_2.png) [@Vlix](https://discourse.haskell.org/u/Vlix)\
**Post date:** [February 18, 2024, 10:27pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/6 "2024-02-18T22:27:49Z")

</div>

Isn’t the `[0..4]` notation just syntactic sugar for `enumFromTo` (and also `enumFromThenTo` in the `[0,2..4]` case) and those methods are pretty much always lazy, so basically just a generator. Just like how the `Foldable Range` instance does it (without implying `Monoid`; using `(:)` instead of the `MkRange` constructor; and the rest of the list being a thunk instead of just a number like in `Range`)

So I don’t really know what the `Range` type/instance is trying to fix/improve?

EDIT: I reread a bit and found

> […], if `[0 .. 1000 * 1000]` occurs twice in our program then GHC may float it to the top level and materialise it. That’s a space leak!

Right, that’s a good point, I guess 🤔

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 18, 2024, 11:01pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/7 "2024-02-18T23:01:35Z")

</div>

Sorry, I didn’t click through. Still, your approach is also putting functions in the `Range` data type (in the form of the `Enum` type class). So I don’t expect that to be optimally performant either unless GHC can somehow optimize that away.

---

<div class="post-metadata">

**Author:** ![mikeplus64](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/mikeplus64/32/3998_2.png) [@mikeplus64](https://discourse.haskell.org/u/mikeplus64)\
**Post date:** [February 19, 2024, 12:58am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/8 "2024-02-19T00:58:16Z")

</div>

I have used a type like this before for work projects, inspired by Rust’s range support. I do dislike having to trust GHC to optimise things away that can be expressed directly very easily; at best it’s just adding to my already long compile-times. Relying on both stream-fusion and aggressive inlining to optimise away nested loops like `forM_ [0..n] \x -> forM_ [0..m] \y -> _` just hasn’t worked that well in my experience, though it’s been a while since I last tried.

For Range you could use a pull array like `data Range a = Range { length :: Int#, index :: Int# -> a }` and get pretty good code regardless of how inlining/optimisation turns out. (It’s too bad using `Int#` and co is so cumbersome though.)

The difference is getting the critical information out of `Ord` and `Enum` when you construct the `Range` rather than when you fold over it. I’ve played around with the idea e.g. [https://github.com/mikeplus64/journeyman/blob/b5c30b08d31b2b676061f7f4daabf60994506d8d/src/Data/Function/Vector.hs#L259](https://github.com/mikeplus64/journeyman/blob/b5c30b08d31b2b676061f7f4daabf60994506d8d/src/Data/Function/Vector.hs#L259) linear-base also has one [Data.Array.Polarized.Pull](https://hackage.haskell.org/package/linear-base-0.3.1/docs/Data-Array-Polarized-Pull.html) although

---

<div class="post-metadata">

**Author:** ![mixphix](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/mixphix/32/5629_2.png) [@mixphix](https://discourse.haskell.org/u/mixphix)\
**Post date:** [February 19, 2024, 1:45am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/9 "2024-02-19T01:45:00Z")

</div>

Haskell is an imperative language, so use it like one!

```haskell
main = do
  var <- newIORef (0 :: Int)
  fix \go -> do
    n <- readIORef var
    print n
    if n < 10 then writeIORef var (n + 1) >> go else pure ()

```

---

<div class="post-metadata">

**Author:** ![jackdk](https://avatars.discourse-cdn.com/v4/letter/j/9f8e36/32.png) [@jackdk](https://discourse.haskell.org/u/jackdk)\
**Post date:** [February 19, 2024, 3:37am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/10 "2024-02-19T03:37:04Z")

</div>

> [@mikeplus64](#):
>
> `forM_ [0..n] \x -> forM_ [0..m] \y -> _`

Does `for (liftA2 (,) [0..n] [0..m]) $ \(x, y) -> _` help you out at all?

---

<div class="post-metadata">

**Author:** ![mikeplus64](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/mikeplus64/32/3998_2.png) [@mikeplus64](https://discourse.haskell.org/u/mikeplus64)\
**Post date:** [February 19, 2024, 3:57am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/12 "2024-02-19T03:57:41Z")

</div>

Looking at some GHC Core now. So to be fair to GHC (9.6.4), actually it does turn my original example into a nice loop. Using `liftA2` unfortunately does seem to make it have to instantiate a list to match on. In any case I just don’t think the tradeoff is worth it, it’s not hard to make a simple range type or to write loops the old fashioned way 🙂. I think Rust has it right in making ranges their own type.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [February 19, 2024, 4:04am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/13 "2024-02-19T04:04:24Z")

</div>

> [@tomjaguarpaw](#):
>
> I’m actually surprised I’ve never seen anything like this before.

What about an _interval_ ?

> [@](#):
>
> (page 7 of 11)
> 
> An interval is represented simply as a pair of values:
> 
> ```haskell
> data Ivl a = a `Upto` a
> 
> ```
> 
> [Functional Reactive Animation](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.701.930&rep=rep1&type=pdf) (1997)

But I would have thought `[first, step .. last]` where `first`, `step` and `last` were _all_ constants would be an exceedingly-rare scenario to worry about - at least one would be a parameter in the vast majority of cases…

* * *

> [@mixphix](#):
>
> Haskell is an imperative language, so use it like one!

…and one where said imperativity can also be _encapsulated_, if externally visible side-effects aren’t needed:

```haskell
runST :: (forall s . ST s a) -> a

```

---

<div class="post-metadata">

**Author:** ![BurningWitness](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/burningwitness/32/3665_2.png) [@BurningWitness](https://discourse.haskell.org/u/BurningWitness)\
**Post date:** [February 19, 2024, 5:45am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/14 "2024-02-19T05:45:51Z")

</div>

> [@tomjaguarpaw](#):
>
> Maybe we should have a `Range` type instead?

And then I assume you will point anyone who encounters this incredibly particular problem to that `Range` type instead of any other solution?

> [@mikeplus64](#):
>
> I do dislike having to trust GHC to optimise things away that can be expressed directly very easily

This is not going to change any time soon. Using unboxed datatypes in normal code is tying yourself to GHC internals, which will happily change without notifying you because PVP does not apply.

@mixphix’s answer is ultimately the correct one: the language has the tools for writing imperative code, you don’t need to rely on optimizations here.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 19, 2024, 7:34am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/15 "2024-02-19T07:34:32Z")

</div>

> [@BurningWitness](#):
>
> And then I assume you will point anyone who encounters this incredibly particular problem to that `Range` type instead of any other solution?

I’m not sure what you mean. Are you suggesting this pattern arises rarely? Or that it rarely causes a problem?

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 19, 2024, 7:52am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/16 "2024-02-19T07:52:54Z")

</div>

> [@mixphix](#):
>
> Haskell is an imperative language,

The world’s finest! This is what it looks like in my forthcoming effect system, Bluefin:

```haskell
main = do
  evalState 0 $ \sn -> do
    withJump $ \break -> forever $ do
      n <- get sn
      print n
      when (n >= 0) (jump break)
      modify sn (+ 1)

```

---

<div class="post-metadata">

**Author:** ![BurningWitness](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/burningwitness/32/3665_2.png) [@BurningWitness](https://discourse.haskell.org/u/BurningWitness)\
**Post date:** [February 19, 2024, 8:24am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/17 "2024-02-19T08:24:32Z")

</div>

> [@tomjaguarpaw](#):
>
> Are you suggesting this pattern arises rarely? Or that it rarely causes a problem?

Yes, the pattern is rare, and I don’t expect people to use that in places where performance is critical.

> [@tomjaguarpaw](#):
>
> This is what it looks like in my forthcoming effect system

This doesn’t need effect systems, it just needs a control flow. `ST` (or `IO`) is more than enough for any such case.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 19, 2024, 9:54am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/18 "2024-02-19T09:54:05Z")

</div>

> [@BurningWitness](#):
>
> I don’t expect people to use that in places where performance is critical

Then what would they use instead? That’s in fact the point of my question. What do you use instead of `for_ [1 .. n]` when performance is critical?

> [@BurningWitness](#):
>
> This doesn’t need effect systems

You’re absolutely right! I’m just showing off something I’m proud of.

---

<div class="post-metadata">

**Author:** ![BurningWitness](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/burningwitness/32/3665_2.png) [@BurningWitness](https://discourse.haskell.org/u/BurningWitness)\
**Post date:** [February 19, 2024, 10:50am UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/19 "2024-02-19T10:50:50Z")

</div>

> [@tomjaguarpaw](#):
>
> What do you use instead of `for_ [1 .. n]` when performance is critical?

Now that I think of it you can just write a custom loop:

```haskell
loop :: Monad m => Int -> (Int -> m ()) -> m ()
loop m work = go 1
  where
    go n
      | n > m = pure ()
      | otherwise = do
          work n
          go (n + 1)

```

It’s trivial to test and it can be customized for the specific case that needs it.

* * *

The imperative approach with mutable state becomes a good idea when there are many variables that are updated sparsely, this case doesn’t even need it.

---

<div class="post-metadata">

**Author:** ![michaelpj](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/michaelpj/32/417_2.png) [@michaelpj](https://discourse.haskell.org/u/michaelpj)\
**Post date:** [February 19, 2024, 5:44pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/20 "2024-02-19T17:44:47Z")

</div>

The loop approach is I think the best one if you really _really_ care about performance.

I think from when I last looked into it:

1. Passing arguments to functions is much faster than getting them into and out of `IORef`s
2. Values in `IORef`s are _not_ unboxed (this can matter a lot), but GHC will pretty-reliably use worker-wrapper to unbox the `Int` argument to a function.

I don’t know of any approach faster than passing an unboxed `Int#` as a function argument.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 19, 2024, 6:31pm UTC](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826/21 "2024-02-19T18:31:23Z")

</div>

Does anyone have an actual example where GHC (9.8) floats out an enumeration `[a..b]` when fusion would otherwise be possible?

[Next page](https://discourse.haskell.org/t/does-it-make-sense-to-have-a-range-data-type/8826.md?page=2)