{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/11879","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/11879/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/11879/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/11879/events","html_url":"https://github.com/JuliaLang/julia/issues/11879","id":91269384,"number":11879,"title":"Rename and generalize the linear indexing trait?","user":{"login":"mbauman","id":154641,"avatar_url":"https://avatars.githubusercontent.com/u/154641?v=3","gravatar_id":"","url":"https://api.github.com/users/mbauman","html_url":"https://github.com/mbauman","followers_url":"https://api.github.com/users/mbauman/followers","following_url":"https://api.github.com/users/mbauman/following{/other_user}","gists_url":"https://api.github.com/users/mbauman/gists{/gist_id}","starred_url":"https://api.github.com/users/mbauman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mbauman/subscriptions","organizations_url":"https://api.github.com/users/mbauman/orgs","repos_url":"https://api.github.com/users/mbauman/repos","events_url":"https://api.github.com/users/mbauman/events{/privacy}","received_events_url":"https://api.github.com/users/mbauman/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-06-26T14:46:53Z","updated_at":"2015-07-08T16:32:00Z","closed_at":null,"body":"In describing `linearindexing` and the new AbstractArray interface to folks here, I am consistently finding myself using the words \"intrinsic dimensionality.\"  A LinearFast array intrinsically works with a one-dimensional index (e.g., as a linear index into a big blob of memory).  A LinearSlow array intrinsically works at the dimensionality of the array, requiring all `N` indices in order to access its elements (e.g., as a `NTuple{N,Int}` key of a dictionary).  These names originated in order to describe how `eachindex` iterates over the indices: either linear indexing is fast (so use it), or it's slow (so use CartesianIndices at the full dimensionality instead).\r\n\r\nBut now with the new abstract fallbacks, the linearindexing trait takes a much more prominent role.  It now determines the dimensionality of the indexing signatures that must be implemented.  These also aren't the only two options there are.  For example, a sparse compressed column datastructure is intrinsically two-dimensional, but it could potentially charade as a vector or 3-dimensional array.  While this definitely isn't optimal, it is a way to quickly get the semantics correct.  This cannot be expressed with the current traits.\r\n\r\nSo what if we renamed `linearindexing` to more aptly describe it as the intrinsic dimensionality?  There are two issues:\r\n\r\n* I don't have a good short name.  `intrinsicdimensionality` is more than a mouthful.\r\n* It needs to return something in the type domain instead of just an integer.\r\n\r\nHere's a quick sketch:\r\n\r\n```jl\r\ntype IntrinsicDimensinality{N}; end\r\nintrinsic_dimensionality(A::Array) = IntrinsicDimensinality{1} # LinearFast()\r\nintrinsic_dimensionality{_,N}(A::DictArray{_,N}) = IntrinsicDimensinality{N} # LinearSlow()\r\nintrinsic_dimensionality(A::SparseCSC) =  IntrinsicDimensinality{2} # New functionality!\r\n```\r\n\r\nAs a bonus, we then would get a real name for this operation: https://github.com/JuliaLang/julia/commit/429713502b3b3e59d96e20326bc89a491ca5570e#commitcomment-11513102: that code is actually asking for the maximum intrinsic dimensionality."},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/119651464","html_url":"https://github.com/JuliaLang/julia/issues/11879#issuecomment-119651464","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/11879","id":119651464,"user":{"login":"mbauman","id":154641,"avatar_url":"https://avatars.githubusercontent.com/u/154641?v=3","gravatar_id":"","url":"https://api.github.com/users/mbauman","html_url":"https://github.com/mbauman","followers_url":"https://api.github.com/users/mbauman/followers","following_url":"https://api.github.com/users/mbauman/following{/other_user}","gists_url":"https://api.github.com/users/mbauman/gists{/gist_id}","starred_url":"https://api.github.com/users/mbauman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mbauman/subscriptions","organizations_url":"https://api.github.com/users/mbauman/orgs","repos_url":"https://api.github.com/users/mbauman/repos","events_url":"https://api.github.com/users/mbauman/events{/privacy}","received_events_url":"https://api.github.com/users/mbauman/received_events","type":"User","site_admin":false},"created_at":"2015-07-08T16:32:00Z","updated_at":"2015-07-08T16:32:00Z","body":"Another example: I would currently consider the dict-backed sparse array type to be `LinearSlow`:\r\n\r\n```jl\r\nimmutable DictSparse{T,N} <: AbstractArray{T,N}\r\n    data::Dict{NTuple{N,Int}, T}\r\n    dims::NTuple{N,Int}\r\nend\r\ngetindex{T,N}(A::DictSparse{T,N}, I::Vararg{N,Int}) = get(A.data, I, zero(T)) # Assuming #11242\r\n```\r\n\r\nBut in actuality, it's linear indexing trait should be defined as:\r\n\r\n```jl\r\ntypealias DictSparseVector{T} DictSparse{T, 1}\r\nBase.linearindexing{A<:DictSparseVector}(::Type{A}) = Base.LinearFast()\r\nBase.linearindexing{A<:DictSparse}(::Type{A}) = Base.LinearSlow()\r\n```\r\n\r\nThis overlap between `LinearFast` and `LinearSlow` vectors also causes complications on the algorithm design front: #12066."}}