Какие типы систем являются достаточно мощными, чтобы выразить это?

Question

Предположим, что мы определяем интерфейс следующим образом:

interface Hashable {
   int hash();
}

Теперь мы можем создавать классы, которые реализуют этот интерфейс.Например, класс List:

class List<T> : Hashable {
   int hash(){
      int h = 0;
      foreach(x in this){
         h = combineHash(h,x.hash());
      }
      return h;
   }
}

Проблема в том, что мы вызываем хеш для элементов внутри List<T>, поэтому T должно быть Hashable.Таким образом, мы должны сделать:

class List<T : Hashable> : Hashable {
   ... same here ...
}

С другой стороны, мы также хотим иметь возможность создавать списки с элементами, которые не могут быть хешируемыми.В этом случае мы просто не хотим, чтобы List<T> реализовал Hashable.Итак:

List<AHashableType>      is itself Hashable
List<NotAHashableType>   is not Hashable

Кроме того, мы хотим, чтобы метод хеширования был полиморфным (тип OO полиморфный, а не параметрически полиморфный).Поэтому, если мы создадим List<Foo> с Bar и Baz внутри, где Foo - это Hashable, а Bar и Baz - это подтипы Foo с различными hash() методамитогда List<Foo>.hash() должен вызывать правильный метод хеширования во время выполнения.

Это кажется основной вещью, которую языки должны уметь выражать.Один и тот же шаблон встречается в разных случаях, например, с ToString() и с IComparable.До сих пор я не нашел языка и решения на этом языке, который позволил бы мне выразить это безопасным способом.Знаете ли вы о таком языке и решении этого языка?Haskell довольно близко подходит к своим классам типов, но, к сожалению, они отправляются во время компиляции.

Answer 1

К сожалению, вам нужно кое-что, как ограничение условного типа для универсальных шаблонов (шаблоны заметок могут поддерживать это посредством частичной специализации и частного наследования). Я не знаю статически типизированный язык, который имеет их, но может быть решен с помощью monkeypatching с помощью методов расширения. Вот пример в C #.

public static int GetHash<T>(this List<T> list) where T:IEquatable<T>
{
      if(list == null) throw new ArgumentNullException("list");
      int h = 0;
      foreach(var x in list){
         h = CombineHash(h,x.GetHashCode());
      }
      return h;
}

Где CombineHash объединяет ваши хэш-коды. Обратите внимание, что каждый метод в C # на самом деле имеет хеш-код по умолчанию, но IEquatable<T> является интерфейсом, который указывает GetHashCode в качестве члена. Таким образом, List<int>. может вызывать GetHash, но List<object> не может, поскольку object не реализует интерфейс. Поскольку GetHashCode не особенно интересен, скажем, мы сделали это:

interface IFoo{
    string Bar();
}
class Foo:IFoo{
    public virtual string Bar(){return "Foo";}
}
class Baz:Foo{
     public override string Bar(){return "Baz";}
}
public static string Bar(this List<T> list) where T:IFoo
{
    if(list == null) throw new ArgumentNullException("list");
    StringBuilder sb = new StringBuilder();
    foreach(var x in list){
       sb.Append(x.Bar());
    }
    return sb.Bar();
}

Здесь, поскольку мы ограничены T Чтобы быть IFoo, мы теперь можем вызывать этот метод либо для List<IFoo>, List<Foo>, либо List<Baz>, но не для List<int> как int не реализует IFoo. например, * * 1 022

public static void SomeMethod()
{
      Console.WriteLine(new List<IFoo>{new Baz(),new Foo()}.Bar()); //compiles
      Console.WriteLine(new List<int>{1,2,3,4,}.Bar()); // does not compile.
}

Answer 2

Может быть, я неправильно читаю ОП, но кажется, что во время компиляции необходимо знать, было ли данное List Hashable или нет. В противном случае, что произойдет с вызовом hash() для не Hashable List?

Я уверен, однако, что решение существует с CLOS. (Многократная диспетчеризация, безусловно, пригодится, и я смутно осознаю ее более выразительный способ работы с подклассами.)

Answer 3

Я думаю, что полезно разделить две проблемы, которые вы описали. Первый - это условно реализовать интерфейс. Как вы сказали, классы типа Haskell делают это. Это будет выглядеть примерно так:

class Hashable t where
  hash :: t -> Int

instance Hashable Int where
  hash i = i

-- Reads as "(List t) is Hashable if t is Hashable"
instance (Hashable t) => Hashable (List t) where
  hash l = ...

Вторая проблема - полиморфизм ОО, который вы можете имитировать в Haskell с помощью механизма, аналогичного указателю на функцию.

-- Pretending we have some kind of OO method dispatch here
instance Hashable Foo where
    hash foo = foo.computeHash()

class Foo
   computeHash()

Я прочитал пару статей, в которых этот вид «реализации условного интерфейса» добавлен к языку, подобному Java. Одним из них является JavaGI (http://homepages.cwi.nl/~ralf/JavaGI/),, который также добавляет возможность реализовать интерфейс для типа данных, который вы изначально не определяли (например, классы типов Haskell). Я не могу вспомнить, как называлась другая статья. *

Answer 4

Проблема, которую вы описываете, является ИМХО хорошим оправданием для того, чтобы идти против принципа разделения интерфейса в ряде ситуаций, особенно в системах ограниченного типа, таких как Java или .NET. Хотя очень важно иметь возможность использовать проверку типов в качестве средства обеспечения того, чтобы объекты запрашивали только те действия, на которые они способны, не все вопросы о способностях могут быть решены до запуска программы. Существует много ситуаций, когда код получает ссылку на объект с дополнительными возможностями, которые он должен использовать, если присутствует, и обходить, если нет. Если интерфейс включает в себя методы для таких необязательных способностей, а также средство определения того, следует ли использовать эти методы, то композиции или совокупности таких объектов также могут раскрывать такие необязательные возможности. Если интерфейсы включают в себя только те действия, которые гарантированно могут выполнять исполнители, то при построении неизменяемая агрегация должна идентифицировать все способности, которые она когда-либо захочет рекламировать, а изменяемая агрегация не может рекламировать любые способности, которые им не потребуются от каждого элемента это добавлено.

Если есть способность, которая будет у некоторых реализаций интерфейса, а у других - нет, и если существует значительная вероятность того, что одни и те же объекты будут иметь дело с вещами, которые имеют способность, и вещами, которые не имеют и должны быть в состоянии использовать такую ​​способность, когда она есть, я бы предложил включить эту способность в интерфейс вместе со средством определения, когда она доступна. Например, если коллекция идентифицирует IFoo экземпляров, некоторые из которых могут Boz(), а сама коллекция должна реализовывать IFoo, а вызов Boz для коллекции должен быть допустимым тогда и только тогда, когда все элементы могут Boz Я бы предложил IFoo включить Boz() вместе со свойством CanBoz. Свойство CanBoz может запрашивать каждый элемент в коллекции, может ли оно Boz, и возвращать утвердительный ответ только тогда, когда все содержащиеся в нем элементы делают это. Вы потеряли бы гарантии времени компиляции, которые могли бы прийти от более строгой проверки типов, но вы получили бы возможность использовать метод в тех случаях, когда статическая проверка типов не могла позволить это.