1--[[-- 2 Tables as lists. 3 4 Prototype Chain 5 --------------- 6 7 table 8 `-> Object 9 `-> List 10 11 @classmod std.list 12]] 13 14 15local base = require "std.base" 16local debug = require "std.debug" 17 18local Object = require "std.object" {} 19 20local ipairs, pairs = base.ipairs, base.pairs 21local len = base.len 22local compare = base.compare 23local prototype = base.prototype 24local unpack = base.unpack 25 26local M, List 27 28 29local function append (l, x) 30 local r = l {} 31 r[#r + 1] = x 32 return r 33end 34 35 36local function concat (l, ...) 37 local r = List {} 38 for _, e in ipairs {l, ...} do 39 for _, v in ipairs (e) do 40 r[#r + 1] = v 41 end 42 end 43 return r 44end 45 46 47local function rep (l, n) 48 local r = List {} 49 for i = 1, n do 50 r = concat (r, l) 51 end 52 return r 53end 54 55 56local function sub (l, from, to) 57 local r = List {} 58 local lenl = len (l) 59 from = from or 1 60 to = to or lenl 61 if from < 0 then 62 from = from + lenl + 1 63 end 64 if to < 0 then 65 to = to + lenl + 1 66 end 67 for i = from, to do 68 r[#r + 1] = l[i] 69 end 70 return r 71end 72 73 74 75--[[ ================= ]]-- 76--[[ Public Interface. ]]-- 77--[[ ================= ]]-- 78 79 80local function X (decl, fn) 81 return debug.argscheck ("std.list." .. decl, fn) 82end 83 84 85M = { 86 --- Append an item to a list. 87 -- @static 88 -- @function append 89 -- @tparam List l a list 90 -- @param x item 91 -- @treturn List new list with *x* appended 92 -- @usage 93 -- longer = append (short, "last") 94 append = X ("append (List, any)", append), 95 96 --- Compare two lists element-by-element, from left-to-right. 97 -- @static 98 -- @function compare 99 -- @tparam List l a list 100 -- @tparam List|table m another list, or table 101 -- @return -1 if *l* is less than *m*, 0 if they are the same, and 1 102 -- if *l* is greater than *m* 103 -- @usage 104 -- if a_list:compare (another_list) == 0 then print "same" end 105 compare = X ("compare (List, List|table)", compare), 106 107 --- Concatenate the elements from any number of lists. 108 -- @static 109 -- @function concat 110 -- @tparam List l a list 111 -- @param ... tuple of lists 112 -- @treturn List new list with elements from arguments 113 -- @usage 114 -- --> {1, 2, 3, {4, 5}, 6, 7} 115 -- list.concat ({1, 2, 3}, {{4, 5}, 6, 7}) 116 concat = X ("concat (List, List|table...)", concat), 117 118 --- Prepend an item to a list. 119 -- @static 120 -- @function cons 121 -- @tparam List l a list 122 -- @param x item 123 -- @treturn List new list with *x* followed by elements of *l* 124 -- @usage 125 -- --> {"x", 1, 2, 3} 126 -- list.cons ({1, 2, 3}, "x") 127 cons = X ("cons (List, any)", function (l, x) return List {x, unpack (l)} end), 128 129 --- Repeat a list. 130 -- @static 131 -- @function rep 132 -- @tparam List l a list 133 -- @int n number of times to repeat 134 -- @treturn List *n* copies of *l* appended together 135 -- @usage 136 -- --> {1, 2, 3, 1, 2, 3, 1, 2, 3} 137 -- list.rep ({1, 2, 3}, 3) 138 rep = X ("rep (List, int)", rep), 139 140 --- Return a sub-range of a list. 141 -- (The equivalent of @{string.sub} on strings; negative list indices 142 -- count from the end of the list.) 143 -- @static 144 -- @function sub 145 -- @tparam List l a list 146 -- @int[opt=1] from start of range 147 -- @int[opt=#l] to end of range 148 -- @treturn List new list containing elements between *from* and *to* 149 -- inclusive 150 -- @usage 151 -- --> {3, 4, 5} 152 -- list.sub ({1, 2, 3, 4, 5, 6}, 3, 5) 153 sub = X ("sub (List, ?int, ?int)", sub), 154 155 --- Return a list with its first element removed. 156 -- @static 157 -- @function tail 158 -- @tparam List l a list 159 -- @treturn List new list with all but the first element of *l* 160 -- @usage 161 -- --> {3, {4, 5}, 6, 7} 162 -- list.tail {{1, 2}, 3, {4, 5}, 6, 7} 163 tail = X ("tail (List)", function (l) return sub (l, 2) end), 164} 165 166 167 168--[[ ============= ]]-- 169--[[ Deprecations. ]]-- 170--[[ ============= ]]-- 171 172-- This entire section can be deleted in due course, with just one 173-- additional small correction noted in FIXME comments in the List 174-- object constructor at the end of this file. 175 176 177local DEPRECATED = debug.DEPRECATED 178 179 180local function depair (ls) 181 local t = {} 182 for _, v in ipairs (ls) do 183 t[v[1]] = v[2] 184 end 185 return t 186end 187 188 189local function enpair (t) 190 local ls = List {} 191 for i, v in pairs (t) do 192 ls[#ls + 1] = List {i, v} 193 end 194 return ls 195end 196 197 198local function filter (pfn, l) 199 local r = List {} 200 for _, e in ipairs (l) do 201 if pfn (e) then 202 r[#r + 1] = e 203 end 204 end 205 return r 206end 207 208 209local function flatten (l) 210 local r = List {} 211 for v in base.leaves (ipairs, l) do 212 r[#r + 1] = v 213 end 214 return r 215end 216 217 218local function foldl (fn, d, t) 219 if t == nil then 220 local tail = {} 221 for i = 2, len (d) do tail[#tail + 1] = d[i] end 222 d, t = d[1], tail 223 end 224 return base.reduce (fn, d, base.ielems, t) 225end 226 227 228local function foldr (fn, d, t) 229 if t == nil then 230 local u, last = {}, len (d) 231 for i = 1, last - 1 do u[#u + 1] = d[i] end 232 d, t = d[last], u 233 end 234 return base.reduce ( 235 function (x, y) return fn (y, x) end, d, base.ielems, base.ireverse (t)) 236end 237 238 239local function index_key (f, l) 240 local r = {} 241 for i, v in ipairs (l) do 242 local k = v[f] 243 if k then 244 r[k] = i 245 end 246 end 247 return r 248end 249 250 251local function index_value (f, l) 252 local r = {} 253 for i, v in ipairs (l) do 254 local k = v[f] 255 if k then 256 r[k] = v 257 end 258 end 259 return r 260end 261 262 263local function map (fn, l) 264 local r = List {} 265 for _, e in ipairs (l) do 266 local v = fn (e) 267 if v ~= nil then 268 r[#r + 1] = v 269 end 270 end 271 return r 272end 273 274 275local function map_with (fn, ls) 276 return map (function (...) return fn (unpack (...)) end, ls) 277end 278 279 280local function project (x, l) 281 return map (function (t) return t[x] end, l) 282end 283 284 285local function relems (l) return base.ielems (base.ireverse (l)) end 286 287 288local function reverse (l) return List (base.ireverse (l)) end 289 290 291local function shape (s, l) 292 l = flatten (l) 293 -- Check the shape and calculate the size of the zero, if any 294 local size = 1 295 local zero 296 for i, v in ipairs (s) do 297 if v == 0 then 298 if zero then -- bad shape: two zeros 299 return nil 300 else 301 zero = i 302 end 303 else 304 size = size * v 305 end 306 end 307 if zero then 308 s[zero] = math.ceil (len (l) / size) 309 end 310 local function fill (i, d) 311 if d > len (s) then 312 return l[i], i + 1 313 else 314 local r = List {} 315 for j = 1, s[d] do 316 local e 317 e, i = fill (i, d + 1) 318 r[#r + 1] = e 319 end 320 return r, i 321 end 322 end 323 return (fill (1, 1)) 324end 325 326 327local function transpose (ls) 328 local rs, lenls, dims = List {}, len (ls), map (len, ls) 329 if len (dims) > 0 then 330 for i = 1, math.max (unpack (dims)) do 331 rs[i] = List {} 332 for j = 1, lenls do 333 rs[i][j] = ls[j][i] 334 end 335 end 336 end 337 return rs 338end 339 340 341local function zip_with (ls, fn) 342 return map_with (fn, transpose (ls)) 343end 344 345 346local m = { 347 append = M.append, 348 compare = M.compare, 349 concat = M.concat, 350 cons = M.cons, 351 rep = M.rep, 352 sub = M.sub, 353 tail = M.tail, 354} 355 356 357m.depair = DEPRECATED ("38", "'std.list:depair'", depair) 358m.map_with = DEPRECATED ("38", "'std.list:map_with'", 359 function (self, fn) return map_with (fn, self) end) 360m.transpose = DEPRECATED ("38", "'std.list:transpose'", transpose) 361m.zip_with = DEPRECATED ("38", "'std.list:zip_with'", zip_with) 362 363 364M.depair = DEPRECATED ("41", "'std.list.depair'", depair) 365 366M.enpair = DEPRECATED ("41", "'std.list.enpair'", enpair) 367m.enpair = DEPRECATED ("41", "'std.list:enpair'", enpair) 368 369M.elems = DEPRECATED ("41", "'std.list.elems'", 370 "use 'std.ielems' instead", base.ielems) 371m.elems = DEPRECATED ("41", "'std.list:elems'", 372 "use 'std.ielems' instead", base.ielems) 373 374M.filter = DEPRECATED ("41", "'std.list.filter'", 375 "use 'std.functional.filter' instead", filter) 376m.filter = DEPRECATED ("41", "'std.list:filter'", 377 "use 'std.functional.filter' instead", 378 function (self, p) return filter (p, self) end) 379 380 381M.flatten = DEPRECATED ("41", "'std.list.flatten'", 382 "use 'std.functional.flatten' instead", flatten) 383m.flatten = DEPRECATED ("41", "'std.list:flatten'", 384 "use 'std.functional.flatten' instead", flatten) 385 386 387M.foldl = DEPRECATED ("41", "'std.list.foldl'", 388 "use 'std.functional.foldl' instead", foldl) 389m.foldl = DEPRECATED ("41", "'std.list:foldl'", 390 "use 'std.functional.foldl' instead", 391 function (self, fn, e) 392 if e ~= nil then return foldl (fn, e, self) end 393 return foldl (fn, self) 394 end) 395 396M.foldr = DEPRECATED ("41", "'std.list.foldr'", 397 "use 'std.functional.foldr' instead", foldr) 398m.foldr = DEPRECATED ("41", "'std.list:foldr'", 399 "use 'std.functional.foldr' instead", 400 function (self, fn, e) 401 if e ~= nil then return foldr (fn, e, self) end 402 return foldr (fn, self) 403 end) 404 405M.index_key = DEPRECATED ("41", "'std.list.index_key'", 406 "compose 'std.functional.filter' and 'std.table.invert' instead", 407 index_key) 408m.index_key = DEPRECATED ("41", "'std.list:index_key'", 409 function (self, fn) return index_key (fn, self) end) 410 411 412M.index_value = DEPRECATED ("41", "'std.list.index_value'", 413 "compose 'std.functional.filter' and 'std.table.invert' instead", 414 index_value) 415m.index_value = DEPRECATED ("41", "'std.list:index_value'", 416 function (self, fn) return index_value (fn, self) end) 417 418 419M.map = DEPRECATED ("41", "'std.list.map'", 420 "use 'std.functional.map' instead", map) 421m.map = DEPRECATED ("41", "'std.list:map'", 422 "use 'std.functional.map' instead", 423 function (self, fn) return map (fn, self) end) 424 425 426 427M.map_with = DEPRECATED ("41", "'std.list.map_with'", 428 "use 'std.functional.map_with' instead", map_with) 429 430M.project = DEPRECATED ("41", "'std.list.project'", 431 "use 'std.table.project' instead", project) 432m.project = DEPRECATED ("41", "'std.list:project'", 433 "use 'std.table.project' instead", 434 function (self, x) return project (x, self) end) 435 436M.relems = DEPRECATED ("41", "'std.list.relems'", 437 "compose 'std.ielems' and 'std.ireverse' instead", relems) 438m.relems = DEPRECATED ("41", "'std.list:relems'", relems) 439 440M.reverse = DEPRECATED ("41", "'std.list.reverse'", 441 "compose 'std.list' and 'std.ireverse' instead", reverse) 442m.reverse = DEPRECATED ("41", "'std.list:reverse'", 443 "compose 'std.list' and 'std.ireverse' instead", reverse) 444 445M.shape = DEPRECATED ("41", "'std.list.shape'", 446 "use 'std.table.shape' instead", shape) 447m.shape = DEPRECATED ("41", "'std.list:shape'", 448 "use 'std.table.shape' instead", 449 function (t, l) return shape (l, t) end) 450 451M.transpose = DEPRECATED ("41", "'std.list.transpose'", 452 "use 'std.functional.zip' instead", transpose) 453 454M.zip_with = DEPRECATED ("41", "'std.list.zip_with'", 455 "use 'std.functional.zip_with' instead", zip_with) 456 457 458 459--[[ ================== ]]-- 460--[[ Type Declarations. ]]-- 461--[[ ================== ]]-- 462 463 464--- An Object derived List. 465-- @object List 466 467List = Object { 468 -- Derived object type. 469 _type = "List", 470 _functions = M, -- FIXME: remove this when DEPRECATIONS have gone 471 __index = m, -- FIXME: `__index = M` when DEPRECATIONS have gone 472 473 ------ 474 -- Concatenate lists. 475 -- @function __concat 476 -- @tparam List l a list 477 -- @tparam List|table m another list, or table (hash part is ignored) 478 -- @see concat 479 -- @usage 480 -- new = alist .. {"append", "these", "elements"} 481 __concat = concat, 482 483 ------ 484 -- Append element to list. 485 -- @function __add 486 -- @tparam List l a list 487 -- @param e element to append 488 -- @see append 489 -- @usage 490 -- list = list + "element" 491 __add = append, 492 493 ------ 494 -- List order operator. 495 -- @function __lt 496 -- @tparam List l a list 497 -- @tparam List m another list 498 -- @see compare 499 -- @usage 500 -- max = list1 > list2 and list1 or list2 501 __lt = function (list1, list2) return compare (list1, list2) < 0 end, 502 503 ------ 504 -- List equality or order operator. 505 -- @function __le 506 -- @tparam List l a list 507 -- @tparam List m another list 508 -- @see compare 509 -- @usage 510 -- min = list1 <= list2 and list1 or list2 511 __le = function (list1, list2) return compare (list1, list2) <= 0 end, 512} 513 514 515return List 516