sw17ch / data-clist Goto Github PK

data-clist compiles fine with deepseq 1.4.1.1 when the cabal bound is removed.

As stated here,

if x == y = True and f is a "public" function whose return type is an instance of Eq, then f x == f y = True

Currently we have, e.g.

>  fromList [1,2,3] == fromList [2,3,1]
True
> toList (fromList [1,2,3]) == toList (fromList [2,3,1])
False

I think that the Eq instance should be just derived and current implementation should be exported as separate function. Besides, using allRotations is surely not the most optimal way of implementing the desired behavior. What if two CLists contain different sets of elements? Current implementation will check all the rotations, while it is possible to return False after finding the first element which is present in one of the given CLists but not in the other.

As the title suggests; can we add Foldable and Traversable instances? This would give us many functions (i.e. minimum, maximum, sum, traverse, etc) for free.

See jtdaugherty/brick#189

GHC 9.8 bundles deepseq-1.5, which is excluded by data-clist upper bound:

 [__6] next goal: data-clist (dependency of brick)
[__6] rejecting: data-clist-0.2, data-clist-0.1.2.3, data-clist-0.1.2.2, data-clist-0.1.2.1, data-clist-0.1.2.0, data-clist-0.1.1.0, data-clist-0.1.0.0 (conflict: pretty => deepseq==1.5.0.0/installed-e7ed, data-clist => deepseq>=1.1 && <1.5)
[__6] rejecting: data-clist-0.0.7.4 (conflict: brick => data-clist>=0.1)
[__6] skipping: data-clist-0.0.7.3, data-clist-0.0.7.2, data-clist-0.0.7.1, data-clist-0.0.7, data-clist-0.0.6, data-clist-0.0.5, data-clist-0.0.4, data-clist-0.0.3, data-clist-0.0.2, data-clist-0.0.1 (has the same characteristics that caused the previous version to fail: excluded by constraint '>=0.1' from 'brick')

Thanks for this lib. I'm interested in #16 and brick and stackage, but here's a more focussed issue: are there any plans for a new release of data-clist compatible with QuickCheck 2.13, released in march ?

Can we bump the upperbound on QuickCheck to allow 2.9? That seems to work fine, and is currently blocking me from releasing a new version of one of my own packages. There even seems to be a pr #12 that does this.

The current Foldable instance leads to somewhat weird behaviour in which the elements are produced in a weird order, as evidenced by the following example:

>>> import qualified Data.Foldable as F
>>> import qualified Data.CircularList as C
>>> mapM_ print $ fmap (\cl -> (cl, F.toList cl, C.toList cl)) $ C.allRotations $ C.fromList [0,8,5,4,1]
(fromList [0,8,5,4,1],[0,8,5,1,4],[0,8,5,4,1])
(fromList [8,5,4,1,0],[8,5,0,1,4],[8,5,4,1,0])
(fromList [5,4,1,0,8],[5,8,0,1,4],[5,4,1,0,8])
(fromList [1,0,8,5,4],[1,0,8,5,4],[1,0,8,5,4])
(fromList [4,1,0,8,5],[4,1,0,8,5],[4,1,0,8,5])

I would probably expect Foldable's toList to behave the same way as C.toList

It would be great if you could mention asymptotic running times. I briefly scanned through the code, seems like most should be what you expect, (i.e. O(1) amortized for a single rotate/insert) or O(n) for full traversels. The only exceptions are removeL and removeR, Alternatingly calling removeL and removeR looks like that is going to be expensive (i.e. linear time per operation)?