search

kowainik / slist

♾️ Sized list
https://kowainik.github.io/projects/slist
Mozilla Public License 2.0
46 stars 6 forks source link

Implement fromRange function #9

Closed chshersh closed 4 years ago

chshersh commented 5 years ago

This can be useful as an alternative to [from .. to] syntax in lists. So I propose to add function with the following type:

fromRange :: Int -> Int -> Slist Int
fromRange from to = ...

Probably this function can be generalized further to work not only with Int :thinking:

vrom911 commented 5 years ago

Great idea! Probably it could be generalized to Enum a => a, so I can reuse those functions.

chshersh commented 5 years ago

@vrom911 Sounds nice!

BlackCapCoder commented 5 years ago

SList implements IsList, so you can already use the [from .. to] syntax if you enable XOverloadedLists. Ranges are actually just syntatic sugar for enumFromTo, and with OverloadedLists that is just passed to fromList, so:

fromRange :: Enum a => a -> a -> SList a
fromRange from to = fromList $ enumFromTo from to
chshersh commented 5 years ago

@BlackCapCoder It's true that Slist has IsList instance and it's possible to implement fromRange using the fromList function. However, fromList runs in O(n) time since it's requires to calculate the length of the list. If you use fromList [from .. to] there is no way to know the length of the list in advance.

At the same time it's possible to implement fromRange function in a such way that it runs in constant time without fully evaluating list! So instead of inefficient [from .. to] you get an extremely efficient fromRange from to.

P.S. The IsList typeclass also contains fromListN function which can be used to create data structures from list more efficiently if you know the length of the list in advance. And Slist contains efficient implementation of the fromListN function.

zfnmxt commented 4 years ago

Is there any desire to create an analog of any of the other enum "range" functions, i.e. enumFrom, enumFromThen, and enumFromThenTo?

vrom911 commented 4 years ago

@zfnmxt , I think that fromRange is sufficient at the moment :slightly_smiling_face: