sort and sortBy are not stack safe
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 35/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Stale
- Domain
- backend
Research direction
The issue points to sort and sortBy in src/Data.List.purs lines 447–482. Start by reading those definitions and the existing list sorting tests, then check how the current implementation handles a list of one million elements. Done means both functions sort large lists without a stack overflow; the proposed Array approach is a suggestion to evaluate, not a settled design.
Written by the indexing model from the issue text.
Description
sort $ range 1 1000000
/home/miles/projects/purescript/lists/output/Data.List/index.js:287
return as(new Data_List_Types.Cons(a, ys));
^
RangeError: Maximum call stack size exceeded
at $tco_var_as (/home/miles/projects/purescript/lists/output/Data.List/index.js:287:39)
Should we swap out this current version (which I assume depends on Haskell's laziness) for something that just reuses Array's sortBy? I think that might end up being faster even in situations where we're not having stack issues.
- Dominant language
- PureScript
- Stars
- 61
- Forks
- 50
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 1
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- No contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from purescript/purescript-lists
-
ZipList is BindOpen
Difficulty 4/5 3-5 days Newbie friendliness 35/100
purescript/purescript-lists#219 · 1 comment · 1 reaction ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 48/100
purescript/purescript-lists#218 ·
-
Data.List.NonEmpty.intersect and Data.List.NonEmpty.intersectBy throw when intersection emptyPossibly taken @evaogbe claimed this 1066 days ago. Opengood first issue type: bug
Difficulty 4/5 3-5 days Newbie friendliness 1/100
purescript/purescript-lists#216 · 2 comments ·
-
type: enhancement
Difficulty 4/5 3-5 days Newbie friendliness 25/100
purescript/purescript-lists#197 · 1 comment ·
-
type: enhancement
Difficulty 5/5 Over a week Newbie friendliness 24/100
purescript/purescript-lists#194 · 5 comments ·
All issues in purescript/purescript-lists
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
-
good first issue help wanted
Difficulty 2/5 1-3 hours Newbie friendliness 80/100
Maintainers usually reply within 1 day
-
bug good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
Maintainers usually reply within 1 day
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
milind-soni/OpenMausBot#5829 ·
Maintainers usually reply within 1 day