path: root/impl.bqn

◶ ← {𝕨((𝕨𝔽𝕩)⊑𝕘){𝔽}𝕩}     # LIMITED to number left operand result
⊘ ← {𝕨((1{𝔽}𝕨)-0)◶𝔽‿𝔾 𝕩}
#⊢ ← {𝕩}  # Prevents dyadic negative ⍟
⊣ ← {𝕩}⊘{𝕨}
˜ ← {𝕩𝔽𝕨⊣𝕩}
∘ ← {𝔽𝕨𝔾𝕩}
○ ← {(𝔾𝕨)𝔽𝔾𝕩}
⊸ ← {(𝔽𝕨⊣𝕩)𝔾𝕩}
⟜ ← {(𝕨⊣𝕩)𝔽𝔾𝕩}
⍟ ← {𝕨((𝕨𝔾𝕩)⊑⊢‿𝕗){𝔽}𝕩}   # LIMITED to boolean right operand result

# LIMITED to numeric arguments for scalar cases
√ ← ⋆⟜(÷2)   ⊘ (⋆⟜÷˜)
∧ ←            ×
∨ ←            (+-×)
¬ ← 1+-
< ← {⟨⟩⥊⟨𝕩⟩} ⊘ (¬≤˜)
> ←            (¬≤)
≥ ← !∘0      ⊘ (≤˜)
≢ ↩ IsArray◶⟨⟩‿≢  # LIMITED to monadic case
Length ← (0<0⊑≢)◶⟨1⋄0⊑⊢⟩∘≢
≠ ← Length   ⊘ (¬∘=)
× ↩ 0⊸(<->)  ⊘ ×
| ← ×⟜×      ⊘ {𝕩-𝕨×⌊𝕩÷𝕨}

_fold←{
  ! 1==𝕩
  l←≠v←𝕩 ⋄ F←𝔽
  r←𝕨 (0<l)◶{𝕩⋄Identity f}‿{l↩l-1⋄l⊑𝕩}⊘⊣ 𝕩
  {r↩(𝕩⊑v)F r}⌜(l-1)⊸-⌜↕l
  r
}
´ ← _fold


#⌜
# LAYER 2: Pervasion
# After defining _perv, we apply it to all scalar functions,
# making them pervasive. I'm not going to write that out.

ToArray ← <⍟(¬IsArray)

∾ ← {k←≠𝕨⋄k⊸≤◶⟨⊑⟜𝕨⋄-⟜k⊑𝕩˜⟩⌜↕k+≠𝕩}  # LIMITED to two vector arguments

_eachd←{
  _e←{ # 𝕨 has smaller or equal rank
    k←≠p←≢𝕨 ⋄ q←≢𝕩
    ! ∧´(⊑⟜p=⊑⟜q)⌜↕k
    l←×´(q⊑˜k⊸+)⌜↕q≠⊸-k
    a←⥊𝕨 ⋄ b←⥊𝕩
    q⥊⥊(≠a) (⊑⟜a𝔽l⊸×⊸+⊑b˜)⌜○↕ l
  }
  (>○=)◶⟨𝔽_e⋄𝔽˜_e˜⟩
}

¨ ↩ {(𝔽⌜)⊘(𝔽_eachd○ToArray)}

_perv←{ # Pervasion
  (⊢⊘∨○IsArray)◶⟨𝔽⋄𝔽{𝕨𝔽_perv𝕩}¨⟩
}
⌊ ↩ ⌊        ⊘ ({(𝕨>𝕩)⊑𝕨‿𝕩} _perv)
⌈ ← -∘⌊∘-    ⊘ ({(𝕨<𝕩)⊑𝕨‿𝕩} _perv)

identity ← {(0⊑𝕨){𝕗=𝕩}◶𝕩‿(1⊑𝕨)}´ ⟨+‿0,-‿0,×‿1,÷‿1,⋆‿1,√‿1,∧‿1,∨‿0,|‿0,⌊‿∞,⌈‿¯∞,<‿0,≤‿1,=‿1,≥‿1,>‿0,≠‿0,⊑⟨!∘0⟩⟩


#⌜
# LAYER 3: Remove other limits
# Now all implementations are full except ∾ and ⊑; ↕ is monadic only

Int←IsArray◶⟨⌊⊸=,0⟩
Nat←IsArray◶⟨0⊸≤∧⌊⊸=,0⟩

Deshape←IsArray◶{⟨𝕩⟩}‿⥊
Reshape←{
  ! 1≥=𝕨
  𝕨↩⥊𝕨
  ! ∧´Nat¨𝕨
  l←×´𝕨
  n←×´≢𝕩
  𝕨⥊{
    𝕩(0<n)◶⟨Type⊸(⊣⌜)⋄⥊⊸{⊑⟜𝕨¨n|𝕩}⟩↕l
  }⍟(l≠n)𝕩
}⟜ToArray
⥊ ↩ Deshape        ⊘ Reshape

Range←{
  I←{!Nat𝕩⋄↕𝕩}
  M←{!1==𝕩⋄(<⟨⟩)⥊⊸∾⌜´I¨𝕩}
  IsArray◶I‿M 𝕩
}

match←{¬∘(0⊑𝕨)◶(1⊑𝕨)‿𝕩}´⟨
  ⟨≠○IsArray , 0⟩
  ⟨¬IsArray∘⊢, =⟩
  ⟨≠○=       , 0⟩
  ⟨∨´≠○≢     , 0⟩
  {∧´⥊𝕨Match¨𝕩}
⟩

Depth←IsArray◶0‿{1+0⌈´Depth¨⥊𝕩}

↕ ↩ Range

≡ ← Depth          ⊘ Match
≢ ↩ ≢              ⊘ (¬Match)


#⌜
# LAYER 4: Operators


DropV← {⊑⟜𝕩¨𝕨+↕𝕨-˜≠𝕩}
Cell ← DropV⟜≢
Pair ← {⟨𝕩⟩} ⊘ {⟨𝕨,𝕩⟩}

Merge←{
  c←≢⊑𝕩
  ! ∧´⥊(c≡≢)¨𝕩
  𝕩⊑⟜⥊˜⌜c⥊↕×´c
}⍟(0<≠∘⥊)
> ↩ Merge          ⊘ >
≍ ← >∘Pair
_ranks ← {⟨2⟩⊘⟨1,0⟩((⊣-1+|)˜⟜≠⊑¨<∘⊢)⥊∘𝔽}
_depthOp_←{
  neg←0>n←𝕨𝔾_ranks𝕩 ⋄ F←𝔽
  _d←{
    R←(𝕗+neg)_d
    𝕨(2⥊(neg∧𝕗≥0)∨(0⌈𝕗)≥Pair○≡)◶(⟨R¨⋄R⟜𝕩¨∘⊣⟩≍⟨(𝕨R⊢)¨∘⊢⋄F⟩)𝕩
  }
  𝕨 n _d 𝕩
}
⚇ ← _depthOp_
_rankOp_←{
  k←𝕨(Pair○= (0≤⊢)◶⟨⌊⟜-,0⌈-⟩¨ 𝔾_ranks)𝕩
  Enc←{
    f←⊑⟜(≢𝕩)¨↕𝕨
    c←×´s←𝕨Cell𝕩
    f⥊⊑⟜(⥊𝕩)¨∘((s⥊↕c)+c×⊢)¨↕×´f
  }
  Enc↩(>⟜0+≥⟜=)◶⟨<⊢,Enc,<¨⊢⟩
  > ((0⊑k)Enc𝕨) 𝔽¨ ((1-˜≠)⊸⊑k)Enc𝕩
}
_scan←{
  ! IsArray 𝕩
  ! 1≤=𝕩
  F←𝔽
  {
    r←⥊𝕩 ⋄ l←≠𝕩 ⋄ c←×´1 Cell 𝕩
    {r↩r𝕩_amend˜𝕨F○(⊑⟜r)𝕩}⟜(c⊸+)¨↕c-˜≠r
    (≢𝕩)⥊r
  }⍟(0<≠∘⥊)𝕩
}

` ← _scan
⎉ ← _rankOp_
˘ ← {𝔽⎉¯1}
_insert←{
  ! 1≤=𝕩
  𝕨 𝔽´ <˘𝕩
}
˝ ← _insert


#⌜
# LAYER 5: Structural functions

_onAxes_←{
  F←𝔽
  (𝔾<≡)∘⊣◶{ # One axis
    ! 1≤=𝕩
    𝕨F𝕩
  }‿{ # Multiple axes
    ! 1≥=𝕨
    ! 𝕨≤○≠≢𝕩
    R←{(0⊑⥊𝕨)F(1 DropV 𝕨)⊸R˘𝕩}⍟{0<≠𝕨}
    𝕨R𝕩
  }
}

SelSub←{
  ! IsArray 𝕨
  ! ∧´⥊Int¨ 𝕨
  ! ∧´⥊ 𝕨 (≥⟜-∧<) ≠𝕩
  𝕨↩𝕨+(≠𝕩)×𝕨<0
  𝕨(1≠=∘⊢)◶{
    ⊑⟜𝕩¨𝕨
  }‿{
    c←×´s←1 Cell 𝕩
    ⊑⟜(⥊𝕩)¨(c×𝕨)+⌜s⥊↕c
  }𝕩
}
Select←ToArray⊸(SelSub _onAxes_ 1)
⊏ ← 0⊸Select       ⊘ Select

JoinTo←{
  s←𝕨Pair○≢𝕩
  a←1⌈´k←≠¨s
  ! ∧´1≥a-k
  c←(k¬a)+⟜(↕a-1)⊸⊏¨s
  ! ≡´c
  l←+´(a=k)⊣◶1‿(0⊑⊢)¨s
  (⟨l⟩∾0⊑c)⥊𝕨∾○⥊𝕩
}

Take←{
  T←{
    ! Int 𝕨
    l←≠𝕩
    i←(l+1)|¯1⌈l⌊((𝕨<0)×𝕨+l)+↕|𝕨
    i⊏JoinTo⟜(1⊸Cell⥊Type)⍟(∨´l=i)𝕩
  }
  𝕨 T _onAxes_ 0 (⟨1⟩⥊˜0⌈𝕨-○≠⊢)⊸∾∘≢⊸⥊𝕩
}
Prefixes ← {!1≤=𝕩 ⋄ (↕1+≠𝕩)Take¨<𝕩}
↑ ← Prefixes       ⊘ Take
Drop←{
  s←(≠𝕨)(⊣↑⊢∾˜1⥊˜0⌈-⟜≠)≢𝕩
  ((sׯ1⋆𝕨>0)+(-s)⌈s⌊𝕨)↑𝕩
}
Suffixes ← {!1≤=𝕩 ⋄ (↕1+≠𝕩)Drop¨<𝕩}
↓ ← Suffixes       ⊘ Drop

Windows←{
  ! IsArray 𝕩
  ! 1≥=𝕨
  ! 𝕨≤○≠≢𝕩
  ! ∧´Nat¨⥊𝕨
  s←(≠𝕨)↑≢𝕩
  ! ∧´𝕨≤1+s
  𝕨{(∾⟜(𝕨≠⊸↓≢𝕩)∘≢⥊>)<¨⊸⊏⟜𝕩¨s(¬+⌜○↕⊢)⥊𝕨}⍟(0<≠𝕨)𝕩
}

Reverse ← {!1≤=𝕩 ⋄ (-↕⊸¬≠𝕩)⊏𝕩}
Rotate ← {!Int𝕨 ⋄ l←≠𝕩⋄(l|𝕨+↕l)⊏𝕩} _onAxes_ 0

Indices←{
  ! 1==𝕩
  ! ∧´Nat¨𝕩
  ⟨⟩∾´𝕩⥊¨↕≠𝕩
}
Rep ← Indices⊸⊏
Replicate ← {0<=𝕨}◶(⥊˜⟜≠Rep⊢)‿{!𝕨=○≠𝕩⋄𝕨Rep𝕩} _onAxes_ (1-0=≠)

↕ ↩ ↕              ⊘ Windows
⌽ ← Reverse        ⊘ Rotate
/ ← Indices        ⊘ Replicate


#⌜
# LAYER 6: Everything else

Join←{
  C←(<⟨⟩)⥊⊸∾⌜´⊢  # Cartesian array product
  ! IsArray 𝕩
  s←≢¨𝕩
  d←≠0⊑⥊s
  ! ∧´⥊d=≠¨s
  ! d≥=𝕩
  l←(≢𝕩){(𝕩⊑⟜≢a⊑˜(j=𝕩)⊸×)¨↕𝕨}¨j←↕r←=a←𝕩
  ! (r↑¨s)≡C l
  i←C{p←+´¨↑𝕩⋄(↕0⊑⌽p)-𝕩/¯1↓p}¨l
  >i<¨⊸⊏¨l/𝕩
}⍟(0<≠∘⥊)

Group←{
  ! IsArray 𝕩
  Chk←{!1==𝕩⋄!∧´Int¨𝕩⋄!∧´¯1≤𝕩⋄≠𝕩}
  l←(1<≡)◶Chk‿{!1==𝕩⋄Chk¨𝕩}𝕨
  ! l≤○≠≢𝕩
  ! ∧´l=l≠⊸↑≢𝕩
  (𝕨⊸=/𝕩˜)¨↕1+¯1⌈´⚇1𝕨
}

∾ ↩ Join           ⊘ JoinTo
⊔ ← Group⟜(↕≠⚇1)   ⊘ Group

Pick1←{
  ! 1==𝕨
  ! 𝕨=○≠s←≢𝕩
  ! ∧´Int¨𝕨
  ! ∧´𝕨(≥⟜-∧<)s
  𝕨↩𝕨+s×𝕨<0
  (⥊𝕩)⊑˜0(⊑⟜𝕨+⊑⟜s×⊢)´-↕⊸¬≠𝕨
}
Pickd←(∨´∘⥊IsArray¨∘⊣)◶Pick1‿{Pickd⟜𝕩¨𝕨}
Pick←IsArray◶⥊‿⊢⊸Pickd
⊑ ↩ (0¨∘≢)⊸Pick    ⊘ Pick
◶ ↩ {𝕨((𝕨𝔽𝕩)⊑𝕘){𝔽}𝕩}  # Same definition, new Pick

# Searching
IndexOf←{
  c←1-˜=𝕨
  ! 0≤c
  𝕨 (0<≠𝕨)◶⟨0⎉c∘⊢,(+˝∧`)≢⎉c⎉c‿∞⟩ 𝕩
}
UniqueMask←{
  ! 1≤=𝕩
  u←0↑𝕩
  {(≠u)>⊑u IndexOf 𝕩}◶{u↩u∾𝕩⋄1}‿0˘𝕩
}
Find←{
  r←=𝕨
  ! r≤=𝕩
  𝕨 ≡⎉r (≢𝕨) ↕⎉r 𝕩
}

⊐ ← !∘0            ⊘ IndexOf
∊ ← UniqueMask     ⊘ (⊐˜<≠∘⊢)
⍷ ← ∊⊸/            ⊘ Find

ReorderAxes←{
  𝕩↩<⍟(0=≡)𝕩
  ! 1≥=𝕨
  𝕨↩⥊𝕨
  ! 𝕨≤○≠≢𝕩
  ! ∧´Nat¨⥊𝕨
  r←(=𝕩)-+´¬∊𝕨
  ! ∧´𝕨<r
  𝕨↩𝕨∾𝕨(¬∘∊˜/⊢)↕r
  (𝕨⊸⊏⊑𝕩˜)¨↕⌊´¨𝕨⊔≢𝕩
}
Transpose←(=-1˜)⊸ReorderAxes⍟(0<=)
⍉ ← Transpose      ⊘ ReorderAxes

# Sorting
_cmpLen ← {
  e←𝕨-˜○(∨´0⊸=)𝕩
  c←𝕗
  𝕨(e=0)◶⟨0,e⟩‿{
    c←×c+𝕨-○≠𝕩
    r←𝕨⌊○≠𝕩
    l←𝕨{
      i←+´∧`𝕨=𝕩
      m←×´⊑⟜𝕨¨↕i
      {c↩×-´𝕩⋄m↩m×⌊´𝕩}∘(⊑¨⟜𝕨‿𝕩)⍟(r⊸>)i
      m
    }○(((-1+↕r)+≠)⊸{⊑⟜𝕩¨𝕨})𝕩
    ⟨l,c⟩
  }𝕩
}
_getCellCmp ← {
  Ci←𝔽⋄l←𝕨⋄c←𝕩
  {
    a←𝕨⋄b←𝕩
    S←(l⊸=)◶{S∘(1+𝕩)⍟(0⊸=)a Ci○(𝕩⊸+)b}‿c
    S 0
  }
}
Cmp ← ∨○IsArray◶{ # No arrays
  𝕨(>-<)𝕩 # Assume they're numbers
}‿{ # At least one array
  lc←𝕨(𝕨-○IsArray𝕩)_cmpLen○≢𝕩
  cc ← (⊑⟜(⥊𝕨))⊸Cmp⟜(⊑⟜(⥊𝕩)) _getCellCmp´ lc
  Cc˜0
}

_binSearch ← {
  B ← 𝔽
  {
    R←{𝕨{a←B m←𝕩+h←⌊𝕨÷2⋄(h+a×2|𝕨)R a⊑𝕩‿m}⍟(>⟜1)𝕩}
    1+(𝕩+1)R ¯1
  }⍟(0⊸<)
}
_grade←{
  ! 1≤=𝕩
  m←×´1 Cell 𝕩 ⋄ Ci←𝔽○(⊑⟜(⥊𝕩))
  cc←m Ci _getCellCmp 0
  Ins←{𝕨⊸(≤+<)◶⟨⊑⟜𝕩,i,-⟜1⊑𝕩˜⟩¨↕1+i←≠𝕩}
  ⟨⟩ {𝕩Ins˜(𝕨(Cc≤0˜)˜m×⊑⟜𝕩)_binSearch≠𝕩}´ m×(↕-˜-⟜1)≠𝕩
}
_bins←{
  c←1-˜=𝕨
  ! 0≤c
  ! c≤=𝕩
  lw←×´sw←1 Cell 𝕨
  cw←lw 𝔽○(⊑⟜(⥊𝕨)) _getCellCmp 0
  ! 0⊸<◶⟨1,∧´0≤˜·cw¨⟜(lw⊸+)lw×↕∘-⟜1⟩≠𝕨
  cx←c-˜=𝕩
  sx←cx Cell 𝕩 ⋄ lc←sw 0 _cmpLen sx
  cc ← (⊑⟜(⥊𝕨))⊸𝔽⟜(⊑⟜(⥊𝕩)) _getCellCmp´ lc
  B←(×´sw)⊸×⊸Cc≤0˜
  (≠𝕨) {B⟜𝕩 _binSearch 𝕨}¨ (×´sx) × ⥊⟜(↕×´)⊑⟜(≢𝕩)¨↕cx
}

⍋ ←   Cmp _grade   ⊘ (  Cmp _bins)
⍒ ← -∘Cmp _grade   ⊘ (-∘Cmp _bins)
∧ ↩ ⍋⊸⊏            ⊘ ∧
∨ ↩ ⍒⊸⊏            ⊘ ∨

OccurrenceCount ← ⊐˜(⊢-⊏)⍋∘⍋
ProgressiveIndexOf ← {𝕨⊐○(≍˘⟜OccurrenceCount𝕨⊸⊐)𝕩}
⊒ ← OccurrenceCount⊘ ProgressiveIndexOf

_repeat_←{
  n←𝕨𝔾𝕩
  f←0⊑𝕨⟨𝔽⟩⊘⟨𝕨𝔽⊢⟩𝕩
  l←u←0
  {!Int𝕩⋄l↩l⌊𝕩⋄u↩u⌈𝕩}⚇0 n
  a←𝕩⋄_p←{𝔽∘⊣`(1+𝕩)⥊<a}
  pos←F _p u ⋄ neg←F⁼_p-l
  (|⊑<⟜0⊑pos‿neg˜)⚇0 n
}
⍟ ↩ _repeat_