It’s hard to look at the code on mobile, because:
- the github repo doesn’t exist
- the Internal module where the type is defined is not exposed (thus can’t see it on hackage)
It’s hard to look at the code on mobile, because:
The API looks great to me and I’m happy to see such package existing!
The (from...)
syntax is a clever usage of postfix operators
I have a few ideas and a few potential feature requests. But that can be discussed separately. This is already a huge amount of work for the first release! The Data.List
API is huge and just walking through the entire API and extracting functions that work for infinite lists is a great amount of deal
I personally worry sometimes about functions that can work with infinite lists because they can accidentally hang. For example, the library provides the following function:
find :: (a -> Bool) -> Infinite a -> a
Which is semantically correct, but practically someone accidentally can write the following code which can hang:
ghci> import Data.Time.Clock.POSIX
ghci> now <- getPOSIXTime
ghci> find (> now + 1) (now...) -- or something in this spirit
which is wrong for other reasons, but still, would be nice to avoid introducing new footguns.
I’m thinking about having a functions that accept a limit: how many entries do you look at before stopping? But for now, a warning in the documentation should be enough
As for the original code like this:
head $ filter (`notElem` hashes) $ map showt [0::Int ..]
Sorry, this is just bonkers code to me and simply suboptimal. If someone passes [0::Int ..]
as hashes
, this function hangs. Because I’m afraid of dealing with infinite lists, I would simply write this code differently.
Though, I understand the sentiment of having a drop-in replacement and sometimes it would be nice to work with infinite streams so I’d love to have package like infinite-list
in the ecosystem
It’s also very interesting from the perspective of learning and understanding laziness in Haskell! Not to mention, that it’s really curious to look at the code to learn something new
The Data.List.notElem
function will always get stuck if you pass in an infinite list (and the element is not in the list). If you are really worried about that, then I’d just change it to Data.Vector.notElem
which is guaranteed to get a finite vector as input. In fact, we can’t really know if the notElem
in the given code was from Prelude
or Data.Vector
.
@hasufell there is nothing fancy inside of Data.List.Infinite.Internal
, just
data Infinite a = a :< Infinite a
@ChShersh thanks for the review! I’m happy to hear about potential feature requests; it’s easier for me to make everything in one go.
I’m happy to hear about potential feature requests; it’s easier for me to make everything in one go.
I have only two feature suggestions at the moment:
Have an interleave
function to interleave two infinite lists, like this:
interleave :: Infinite a -> Infinite a -> Infinite a
interleave (x :< xs) (y :< ys) = x :< y :< interleave xs ys
An alternative implementation could be more polymorphic:
interleave :: Infinite a -> Infinite b -> Infinite (Either a b)
interleave (x :< xs) (y :< ys) = Left x :< Right y :< interleave xs ys
I’m happy with everything as I can easily implement one through another but interleaving infinite lists is something I would want quite often.
I wonder what is the trade-off for using Word
instead of Natural
for indexing functions like this one and could this trade-off be documented?
(!!) :: Infinite a -> Word -> a
I understand that returning a number higher that maxBound :: Word
is impossible practically but all other functions that work with lists use Int
and not Word
so it’ll introduce an extra conversion layer.
The behaviour of something like ((maxBound :: Int)...)
is quite unfortunate. Would it be possible to implement some functions that cycle over the entire range of numbers? I imagine having a function like:
cycleFromAscending :: (Enum a, Bounded a) => a -> Infinite a
cycleFromDescending :: (Enum a, Bounded a) => a -> Infinite a
that properly handles the maxBound
and minBound
cases.
That’s all from me Otherwise, it looks great! And I also really appreciate that this package is lightweight! Can’t wait to find a usage for it in my projects
I would perhaps document the Applicative
instance saying that it’s zip-like, unlike the default one for regular lists.
The Semigroup
one is also non-obvious. What if we had a “pointwise mappend” instead? Monoid m => Monoid (Infinite m)
.
@danidiaz that’s interesting points, thanks. I think I’d rather remove instance Semigroup
altogether: the current one with (<>) = const
is quite pointless, and instance Applicative
already provides zip-like semantics.
@danidiaz thinking of ZipList
-like behaviour of instance Applicative Infinite
, I realised that on contrary to ZipList
we can have a lawful instance Monad Infinite
, unlocking list comprehensions syntax under {-# LANGUAGE MonadComprehensions #-}
pragma.
@ChShersh thanks again!
Done, excellent point, I always regret that there is no interleave
in Data.List
.
Using Word
instead of Natural
is a better trade-off performance-wise. Conversion between Int
and Word
is almost free, because on hardware level this is a no-op. And recursive worker with a strict Word
gets unpacked to Word#
, so there are no additional heap allocations. Both of this does not hold for Natural
: conversions to and from Int
require some work, and it cannot easily be unpacked to an unlifted and unboxed value. Given that from practical point of view indices over 2^64 will just hang almost infinitely, I think Word
is a better choice in this case.
That’s a good point, but I’m not sure about extending this API. Morally (...)
is purposed for cases when a list is “practically” infinite: [(0::Int)..]
or [(42::Int)..]
are fine, even while in theory both a finite, but [maxBound..]
is really an edge case, for which I decided to cycle instead of throwing an error.
As a consumer I’d probably prefer to use an explicit iterate
call instead of hypothetical cycleFrom{A,De}scending
, making semantics transparent without refering to documentation. Say, iterate (\n -> if n == maxBound then minBound else n + 1) from
.
I’d love to have (-..) upto = [upto, upto - 1 ..]
, but upto - 1
explodes for upto = 0 :: Natural
, and adding Bounded
constraint to be able to compare upto == minBound
prohibits (-..)
on Integer
.
One possibility is to add
(....) :: (a, a) -> Infinite a
(....) (from, then) = unsafeCycle $ enumFromThen from then
so that (1,3)....
generates an infinite list equal to [1,3..]
, and (maxBound, maxBound-1)....
gives a descending (practically) infinite sequence. Isn’t this too much of syntactic sugar?..
The monad instance bind operator results in:
xs >>= f
= f (xs !! 0) !! 0
:< f (xs !! 1) !! 1
...
Why not fill the front corner with a triangle:
xs >>= f
= f (xs !! 0) !! 0 -- sum 0
:< f (xs !! 0) !! 1 -- sum 1
:< f (xs !! 1) !! 0 -- sum 1
:< f (xs !! 0) !! 2 -- sum 2
:< f (xs !! 1) !! 1 -- sum 2
:< f (xs !! 2) !! 0 -- sum 2
:< f (xs !! 0) !! 3 -- sum 3
...
In this way every element in the result will eventually show up.
@1chb then the Applicative and Monad instances wouldn’t match up. E.g. Control.Monad.ap = (<*>)
would fail to hold.
But couldn’t the Applicative instance be modified in the same way?
Yeah, I guess you can of course always get an applicative from a monad. A better argument would be that the law fmap f x = pure f <*> x
would fail to hold (if my mental math is correct).
@Bodigrim I guess not:
xy z xyz s x yz xyz s
00 0 000 0 == 0 00 000 0
01 1 001 1 == 1 01 001 1
10 2 010 1 /= 2 10 100 1
02 3 002 2 /= 3 02 010 1
11 4 011 2 /= 4 11 101 2
.... 100 1 /= .... 200 2
.... 003 3 /= .... 002 2
.... 012 3 /= .... 110 2
.... 101 2 /= .... 201 3
.... 020 2 /= .... 300 3
.... 004 4 /= .... 011 2
.... 013 4 /= .... 102 3
.... 102 3 /= .... 210 3
.... 021 3 /= .... 301 4
.... 110 2 /= .... 400 4
I am not so fond of the name foldr1
in this library. I personally would prefer it be called foldr
, because it is the standard fold for this data structure.
I guess this name was chosen because you don’t have to give a base case just like foldr1
on lists, but for me the 1
suffix also signifies partiality and the restricted type a -> a -> a
for the first argument. Neither is the case for this fold.
(I mean, this fold over infinite lists is also partial, but it at least has some partial applications (no pun intended) which result in functions that are not partial.)
With regards to partiality, it’s time to change your mental model, the total foldr1 :: Foldable1 t => (a -> a -> a) -> t a -> a
is coming soon in GHC 9.6.
I don’t really know what is worse: foldr :: (a -> b -> b) -> Infinite a -> b
, reducing the number of arguments, or foldr1 :: (a -> b -> b) -> Infinite a -> b
, which is a strictly more polymorphic than Foldable.foldr1
. I chose the second option, but now I see that others find it perplexing. I’m certainly not up to the first one: my poor brain will look for a base argument of foldr
forever. Maybe a completely different name is needed? But foldrInfinite
is too mouthful… I’m open to suggestions.
Thanks, that is good to know.
I guess I have the perspective that folds are just catamorphisms. So I find foldr
very natural for lists (not for other data structures). Other functions like foldr1
and foldl
are just special cases of foldr
.
Now that I’m thinking more about Foldable
, I’m also missing functions like foldMap :: Semigroup m => (a -> m) -> Infinite a -> m
and fold :: Semigroup m => Infinite m -> m
. I guess an argument against adding those is that there are not that many semigroups for which these will terminate.
I thought about cata :: (a -> b -> b) -> Infinite a -> b
, but it might be too scary for uninitiated.