swiftlang/swift

[SR-3444] map, filter on RangeReplaceableCollection should return Self

Open

#46,032 opened on Dec 17, 2016

View on GitHub
 (3 comments) (0 reactions) (0 assignees)Swift (69,989 stars) (10,719 forks)batch import
good first issueimprovementstandard libraryswift evolution proposal needed

Description
Previous ID SR-3444
Radar None
Original Reporter @airspeedswift
Type Improvement
Votes 1
Component/s Standard Library
Labels Improvement, StarterProposal, swift-evolution-proposal-needed
Assignee None
Priority Medium

md5: 05669e9e4e1c642618be3a82e1ececb1

Issue Description:

Currently, map and filter on Sequence return an Array, even though the implementation use only capabilities of Array that are available on RangeReplaceableCollection* (an empty init, reserveCapacity, and append).

This means that RangeReplaceableCollection could implement a version of map that returned the same type. For example, a Deque could return another Deque. This is probably what most users would expect for these types.

This would only apply to RRCs that could hold the mapped-to element type. Also note that, in the case of map, this would only apply to transformations that return the same element type – to represent a transformation to another type would require higher-kinder types. And sequences and non-RRC collections, like Set would need to return arrays.

*(this isn't completely true: it creates a ContiguousArray and then turns it into an Array. But hopefully this optimization could be removed at some point)

Contributor guide

Tech stack
swift
Domain
backend
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
mostly clear
Prerequisites
Swift internalsGeneric programmingProtocol oriented design
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
30
Research direction
The issue proposes changing map and filter on RangeReplaceableCollection to return Self instead of Array. To implement, explore the current implementation in Swift's standard library, likely in files under stdlib/public/core/SequenceAlgorithms.swift.gyb. Understand how map and filter are currently defined on Sequence using ContiguousArray and then converting to Array. Then design a constrained extension on RangeReplaceableCollection that uses Self.init(), reserveCapacity, and append. Note that this only works when the transformation preserves the element type. Consider the performance implications and potential for removing the ContiguousArray intermediate. The discussion in the issue also mentions higher kinded types for different element types. Review comments for any additional constraints.