Перегрузить метод стандартного массива, чтобы принимал регэкспы.

Круто :) В Perl всё есть и всё реализуемо, если бы ещё сам движок оптимизировали и на LLVM перевели.

Блин, да это в любом языке где есть регекспы и функции можно сделать за полвечера.

Единственный болезненный косяк - вообще непонятно, что делать, если между множествами, заданными ключами, есть пересечения? Ну и хотелось бы большей гибкости: часто вполне достаточно pattern glob'ов (нечёткое совпадение) тех же или union'ов (перечислений возможных значений). Да и просто plain text никто не отменял.

Суть в том, чтобы можно было ассоциативно сопоставлять не только вырожденное множество (константу) некоторому значению, но и нормальные множества, описанные в соотв. с той или иной дисциплиной: регулярными выражениями, нечёткими совпадениями, перечислениями, диапазонами...

Но синтаксически это будет выглядеть как костыли или как тяжеловесный ООП-shit с наследованием. На Perl это реализовано легко, просто и понятно (tied variable).

какая у этого сложность получается? O(n)?

Используй Лисп.

В функциональных языках есть Pattern Matching, но там, как правило, нет массивов)

Массивы там есть, в том числе, в Haskell, даже нескольких видов

Здесь слишком сложно родить что-то, что имело бы сложность лучше, чем O(n)

- ищешь библиотеку режекспов для своего любимого яп, такую чтобы давала доступ к потрохам (группировать режекспы через | и именованные группы или просто возможность узнать какой паттерн сработал)

- делаешь ассоциативный массив который унутрях из всех ключей стоит составной режексп (но блин, не конкатенацией строк, хотя если хочется побыдлокодить)

- вуаля

Списки же, не?

списки тоже есть

Динамическому языку от LLVM ни холодно, ни жарко.

Это можно сделать в любом современном (и многих несовременных) языке, только сложность выше линейной сделать будет затруднительно. Вот Ruby:

Glob = Struct.new(:glob) do
  def ===(other)
    (other.is_a?(Glob) && other.glob == glob) || (other.is_a?(String) && File.fnmatch(glob, other))
  end
end

def glob(glob)
  glob.is_a?(Glob) ? glob : Glob.new(glob)
end

class FuzzyHash
  Entry = Struct.new(:key, :value) do
    def ===(other)
      key === other
    end
  end

  def initialize(hash = nil, &block)
    @default = block
    @entries = []

    Hash(hash).each { |key, value| self[key] = value }
  end

  def []=(key, value)
    Entry.new(key, value).tap { |entry| @entries << entry }
  end

  def [](key)
    (@entries.find { |entry| entry === key } || default(key))&.value
  end

  def delete(key)
    @entries.delete_if.with_object([]) do |entry, memo|
      (entry === key).tap { |ret| memo << entry.value if ret }
    end
  end

  def key?(key)
    @entries.any? { |entry| entry === key }
  end

  private

  def default(key)
    return nil if @default.nil?

    ret = @default.call(self, key)

    ret.is_a?(FuzzyHash) ? ret : Entry.new(key, ret)
  end
end

Пример в REPL:

pry(main)> hash = FuzzyHash.new /^(any|key|be|no|key)$/ => 'value', 'hello' => 'world', glob('foo*bar') => 'Dummy stuff', (1..Float::INFINITY) => 'Positive'
=> #<FuzzyHash:0x0000000231dc90
 @default=nil,
 @entries=
  [#<struct FuzzyHash::Entry key=/^(any|key|be|no|key)$/, value="value">,
   #<struct FuzzyHash::Entry key="hello", value="world">,
   #<struct FuzzyHash::Entry key=#<struct Glob glob="foo*bar">, value="Dummy stuff">,
   #<struct FuzzyHash::Entry key=1..Infinity, value="Positive">]>
pry(main)> hash['any']
=> "value"
pry(main)> hash['hello']
=> "world"
pry(main)> hash['fooizmus lebar']
=> "Dummy stuff"
pry(main)> hash[2.5]
=> "Positive"

Че-то ты навыдумывал, не будет такое работать.

Че-то ты навыдумывал, не будет такое работать.

дружок, если ты встретил что-то выше своего понимания, то это не значит что это бред. Быдлокодерский (т.е. возможно понятный тебе) вариант делается на любом яп с режекспами умеющими это:

(?<key1>^(any|key|be|no|key)$)|(?<key2>hello)|(?<key3>foo.*bar)

Fix

--- aaa	2017-06-20 21:39:20.210867569 +0300
+++ bbb	2017-06-20 21:53:28.704220951 +0300
@@ -23,11 +23,11 @@
   end
 
   def []=(key, value)
-    Entry.new(key, value).tap { |entry| @entries << entry }
+     @entries << Entry.new(key, value)
   end
 
   def [](key)
-    (@entries.find { |entry| entry === key } || default(key))&.value
+    @entries.find { |entry| entry === key }&.value || @default&.call(self, key)
   end
 
   def delete(key)
@@ -39,14 +39,4 @@
   def key?(key)
     @entries.any? { |entry| entry === key }
   end
-
-  private
-
-  def default(key)
-    return nil if @default.nil?
-
-    ret = @default.call(self, key)
-
-    ret.is_a?(FuzzyHash) ? ret : Entry.new(key, ret)
-  end
 end

А, вроде бы понял.

Неправильно прочитал твоё сообщение, сорри.

Вот простейшая реализация, если я правильно понял:

class RegexpHash
  def initialize
    @entries = {}
    @capture_name_prefix = "#{self.class.name}:#{object_id}"
    @capture_name_generator = Enumerator.new do |yielder|
      counter = 0
      loop { yielder << "#{@capture_name_prefix}:#{counter += 1}" }
    end
  end

  def [](key)
    match = @matcher&.match(key) or return
    capture = capture_name(match)
    @entries[capture] if capture
  end

  def []=(key, value)
    capture = @capture_name_generator.next
    update_matcher(capture, key)
    @entries[capture] = value
  end

  private

  def generated_capture_name?(name)
    name.start_with?(@capture_name_prefix)
  end

  def capture_name(match)
    match.named_captures.find { |name, value| value && generated_capture_name?(name) }&.first
  end

  def update_matcher(capture, regexp)
    regexp = /(?<#{capture}>#{regexp})/

    @matcher = @matcher.nil? ? regexp : Regexp.union(@matcher, regexp)
  end
end

судя по документации (я в руби не силен) фокус не пройдет т.к.

The behavior is unspecified if any given pattern contains capture.

судя по документации (я в руби не силен) фокус не пройдет т.к.

Несмотря на то, что у меня работает, тут ты, похоже, прав. Другое дело, что для данного конкретного случая легко написать свой вариант Regexp.union.

А в каком-нибудь Rust есть RegexSet, который позволяет 1) сопоставить строку с множеством регулярок за один проход, 2) узнать, какое именно регулярное выражение совпало со строкой.

А в каком-нибудь Rust есть RegexSet, который позволяет 1) сопоставить строку с множеством регулярок за один проход, 2) узнать, какое именно регулярное выражение совпало со строкой.

тогда это именно то что нужно ТСу

Синтаксис у Ruby жутковатый: не люблю языки, которые невозможно понять, не изучая их синтаксис. Впрочем, сам пишу на Perl'е, который без подготовки наверное тоже понять тяжело... Вопрос был всё-таки о языке, в котором авторы заранее подумали о том, что ассоциативные массивы могут быть чуть сложнее простого соответствия строки и значения, но тем не менее предложенное Ruby-решение действительно позволяет добавить недостающий функционал - даже диапазоны есть!

А что всё-таки предложите для пересечения множеств? В общем случае ведь могут пересекаться произвольные множества...

В С++! Вы всегда можете написать шаблон, который сделает что вам нужно.

А что всё-таки предложите для пересечения множеств? В общем случае ведь могут пересекаться произвольные множества...

Так как в данном примере всё равно происходит линейный перебор всех записей, то можно сделать, чтобы возвращались значения для всех совпадающих множеств.

ИМХО давольно специфический функционал чтобы для такого целый ЯП изучать, с другой стороны почти любой динамический типизированый ЯП сможет расшириться (а если лень самому, то можно поискать библиотеки). Например подобной есть в Pandas для Python. Но там скорее обычные массивы, но суть та же, вместо индекса можно передать условие по которому возвращается список элементов

В общем виде это будет работать неэффективно, а потому не нужно. Но если нужен эффективный способ матчинга по нескольким регэкспам с определением номера сработавшего регэкспа, то посмотрите в сторону pire.

Для конечного языка описываемого рег. выражением можно сгенерировать набор ключей. А вот как быть с бесконечным - не ясно.

Разве что сгенерировать все двух-трех буквенныё ключи и в случае совпадения, дальнейшее сравнение проводить при помощи матчинга рег. выражения.

Проблемы с пересекающимися множествами не вижу... новый сгенерированный ключ из пересекающегося множества перепишет старый :)

Меня интересует, видел ли кто-либо что-то подобное в существующих языках или нет?

ИМХО, это делается на коленке за 10 минут практически в любом языке :) Вот работающий пример:

$hash = new PatternHashArray();

$hash[['^(any|key|be|no|key)$', PatternHashArray::REGEXP]] = 'value';
$hash['hello'] = 'world';
$hash[['foo*bar', PatternHashArray::GLOB]] = 'Dummy staff';

dump(
	$hash['any'],
	$hash['hello'],
	$hash['fooizmus lebart'],
	$hash['fooizmus lebar']
);

"value"
"world"
NULL
"Dummy staff"

Проблемы с пересекающимися множествами не вижу... новый сгенерированный ключ из пересекающегося множества перепишет старый :)

Хотя нет, будут проблемы :)

В общем случае не понятно как быть с бесконечными языками, кроме тупого последовательного матчинга.

С другой стороны ключи обычно конечные, потому при первом успешном матчинге можно кэшировать ключ, добавляя его явно в ассоциативный массив (и запоминать ссылку на регэкс). Как потом оттуда потом удалять?... :)

Как бы ни так!

http://hackage.haskell.org/packages/search?terms=array

Даже если предположить, что ключ из пересекающегося множества перепишет все значения для тех множеств, в которые входит - вопрос, как быть с чтением такого ключа, если таки для каждого из множеств, куда он входит, значение исходно какое-то своё. Возможно, имеет смысл вернуть... множество? В смысле, вектор значений и вернуть?

Проблема в том, что это технически неудобно: бьюсь об заклад, что разработчик в 99.9% случаев захочет получить одно конкретное значение и никаких пересекающихся множеств в ключах у него не будет. И конечно то, что ради универсальности ему на всякий случай будут возвращать вектор из одного элемента - будет немного раздражать. Да и удаление от концепции обычных («вырожденных») ассоциативных массивов будет уже слишком заметно.

В Perl есть механизм возврата последнего значения из списка, если из функции возвращается список, а присваивается он скаляру. Есть ли что-то подобное в других языках?

В Perl есть механизм возврата последнего значения из списка, если из функции возвращается список, а присваивается он скаляру. Есть ли что-то подобное в других языках?

В статически типизированных языках с нормальными системами типов есть диспетчеризация по возвращаемому значению.

Вообще бесползеная задача, т.к. все сводится к одному регэксу (или автомату), где в каждом принимающем состоянии свое значение.

Мысль конечно интересная, но вопрос как раз в том и заключается, что по сути-то непонятно, какого типа значение следует возвращать.

Человек передаёт в ассоциативный массив ключ - и ожидает на выходе... чего он ожидает, если он заранее не знает, соответствует ли ключ 1-му значению или нескольким значениям?

Предположим, он ожидает получить ссылку на некий вектор - в таком случае вариант получается универсальным, но косяк в том, что: а) привычный всем «вырожденный» ассоциативный массив так себя не ведёт; б) если на самом деле значение всего одно, а используется «полноценный» А.М. часто - необходимость доставать что-то из вектора будет неминуемо... несколько раздражать.

Если он ожидает получить просто одно значение, то непонятно, как быть в случае с пересечениями: выдать ему произвольное одно значение из N возможных? Или выдать некое UNKNOWN в том или ином виде?

И здесь по-моему вопрос не в том, насколько соверщенны языки того или иного типа, вопрос сугубо логический и... организационный :)

Т.е. нужно прежде всего понимать концептуально, что такое «ассоциации» с точки зрения универсальной системы понятий, не привязанной к IT-технологиям как таковым. Т.е. нужно на минутку вспомнить о том, для чего человек пользуется какими-то языками программирования, а не пишет напрямую машинные коды в hex-редакторе: язык программирования «транслирует» человеческую логику и систему понятий в набор инструкций, понятных исполнительным устройствам.

С моей точки зрения расхожая фраза «это явление вызывает у меня множество ассоциаций» - вполне объясняет то, что да, всё-таки ничего странного нет в том, чтобы возвращать несколько ассоциаций по значению ключа. Это всё равно как если бы Вам сказали «солёный бриз», «ароматная хвоя» - и попросили назвать ассоциации. А.М. полноценного типа как раз и есть по существу модель человеческой ассоциативной памяти.

Другое дело, что также верно и то, что хотелось бы всё-таки влиять на объём получаемой «ассоциативной» информации. Например, если вы хотите получить из памяти испытуемого только одну ассоциацию для «солёного бриза» - Вы, очевидно, должны иметь такую возможность.

Т.е. в действительности для случая полноценного А.М. неизбежны ситуации, когда помимо самого ключа Вам захочется передать хотя бы такой настроечный параметр, как «вид возвращаемого значения: вектор или единичное».

И здесь-то как раз Perl показывает себя весьма неплохо, поскольку в любую возвращающую что-либо функцию там передаётся неявный, но очень полезный параметр: тип контекста вызова. Это значит, что даже в функции, которой передано только значение ключа (tied hash FETCH), как минимум можно узнать, чего от нас хотят сейчас: единичное значение -скаляр или множество значений-вектор.

Но это скорее из области «хаков», а в нормальном общем случае полноценный ассоциативный массив может быть реализован либо синтаксически «похоже» на вырожденные А.М. - как встроенное средство самого ЯП, либо всё-таки - как явный набор методов какого-нибудь «объекта, принадлежащего классу AssocDict» :)

Ненуачо, пусть одному ключу будет соответствовать несколько значений, а поиск значений будет производиться последовательным перебором. Массивы как они есть.

Еще на Ruby можно так.

В этой строке происходит мемоизация. То есть, когда мы ищем ключ первый раз, то это займет O(n) времени, где n — наши паттерны(регекспы и глобы). А все последующие поиски займут амортизированное O(1).

насколько я понял, есть 3 вида ключей (регэксп, текст и глоб), и тип ключа заранее известен

составляем по каждому виду ключей отдельный конечный автомат (регэкспы скорее всего проще оставить как есть, потому что сложность как будет O(sum(len(key) for key in keys)), так и останется; из вайлдкардов и тем более текста можно сделать чёт типа бора, и тогда поиск и добавление будет за O(max(len(key) for key in keys))

чисто теоретически регэкспы можно умно слить, но чересчур уж геморно; или же | сливает их умно?

может здесь пригодится «лень» а-ля итератор? Действительно, зачем отбирать сразу все значения, если надо какое-нибудь одно, ну или несколько, а «ассоциативный словарь» огромен? :)

В js это будет выглядеть

hash = new RegExpHashMap({
   [/\d+(\.\d+)?/]: "contains a number",
   [/s$/]: "ends with an \`s\'"
})

hash[/^(any|key|be|no|key)/] = 'value'

console.log(hash.any) // value
console.log(hash.foo123) // contains a number
console.log(hash.examples) // ends with an \`s\'

Perl?

После того, как появится нормальный. Читал сегодня sbcl-help и угорал, как Стассатс обосновывал, что вызов функции в SBCL не обязан работать нормально.

Читал сегодня sbcl-help и угорал

Все-таки жаваскрипт выжрал тебе моск :(