Есть ли в документации F# способ поиска функций по их типам?

Question

Скажем, я хочу знать, если F# имеет библиотечную функцию типа

('T -> bool) -> 'T list -> int

то есть то, что подсчитывает, сколько элементов списка, для которых функция возвращает true. (или возвращает индекс первого элемента, который возвращает true)

Я использовал большой список на сайте MSR для F# до того, как документация по MSDN была готова. Я мог бы просто найти на странице текст выше, потому что типы были перечислены. Но теперь в документации MSDN перечислены только типы на отдельных страницах - страница модуля представляет собой массу описательного текста. Google вроде-работает, но не может помочь

// compatible interfaces
('T -> bool) -> Seq<'T> -> int
// argument-swaps
Seq<'T> -> ('T -> bool) -> int
// type-variable names
('a -> bool) -> Seq<'a> -> int
// wrappers
('a -> bool) -> 'a list -> option<int>
// uncurried versions
('T -> bool) * 'T list -> int
// .NET generic syntax
('T -> bool) -> List<'T> -> int
// methods
List<'T> member : ('T -> bool) -> int

На Haskell есть отдельная программа для этого под названием Hoogle. Есть ли у F# эквивалент, как Fing или что-то?

Answer 1

Основываясь на ответе kvb, я создал полное приложение. Он размещен на github по адресу http://github.com/sandersn/fing.

Код все еще довольно уродливый, но он работает для простых случаев. Я достал самый универсальный унификатор kvb (mgu) пока что добавляет много неочевидных результатов. Такие причудливые вещи, как структурные ограничения и самый общий супертип, тоже пока не работают.

Есть также двоичный файл для версии из командной строки, если вы не хотите собирать из исходного кода. (Однако для этого все еще требуется современная версия установленной среды выполнения.NET.) В конце концов я найду хостинг ASP.NET, изучу ASP и заверну все это в веб-приложении, так что установка вообще не требуется. (Думаю, если есть спрос, я мог бы создать графический интерфейс на стороне клиента, но у меня еще меньше опыта в подобных вещах.)

Answer 2

Я не знаю ни одного такого инструмента. Тем не менее, это может быть забавное упражнение, чтобы написать один, используя System.Reflection (или, что еще лучше, библиотеку метаданных в PowerPack), чтобы можно было учитывать имена переменных по модулю и т. д.

РЕДАКТИРОВАТЬ - я был прав - это было забавное упражнение. Последующее имеет много бородавок, но не так уж плохо для ~150 строк кода. Надеюсь, этого будет достаточно, чтобы начать кого-то, кто хочет работать над реальным инструментом. Он не делает ничего сложного, например, проверку функций с переупорядоченными параметрами, а библиотека метаданных немного требовательна к использованию полностью определенных имен, поэтому вам нужно быть немного осторожнее. Чтобы ответить на вопрос в вашем оригинальном посте, я выполнил

find "('a -> Microsoft.FSharp.Core.bool) -> Microsoft.FSharp.Collections.list`1<'a> -> Microsoft.FSharp.Core.int" 

и получил следующий список кандидатов:

Microsoft.FSharp.Core.Operators.( + )
Microsoft.FSharp.Core.Operators.( - )
Microsoft.FSharp.Core.Operators.( * )
Microsoft.FSharp.Core.Operators.( / )
Microsoft.FSharp.Core.Operators.( % )
Microsoft.FSharp.Core.Operators.sqrt
Microsoft.FSharp.Core.LanguagePrimitives.EnumOfValue
Microsoft.FSharp.Core.LanguagePrimitives.EnumToValue
Microsoft.FSharp.Core.LanguagePrimitives.AdditionDynamic
Microsoft.FSharp.Core.LanguagePrimitives.CheckedAdditionDynamic
Microsoft.FSharp.Core.LanguagePrimitives.MultiplyDynamic
Microsoft.FSharp.Core.LanguagePrimitives.CheckedMultiplyDynamic
Microsoft.FSharp.Core.LanguagePrimitives.GenericZero
Microsoft.FSharp.Core.LanguagePrimitives.GenericOne
Microsoft.FSharp.Collections.List.find
Microsoft.FSharp.Collections.List.findIndex
Microsoft.FSharp.Collections.List.maxBy
Microsoft.FSharp.Collections.List.minBy

Из них только List.findIndex имеет именно тот универсальный тип, который вы ищете, но с правильной комбинацией параметров типа, так же как и остальные (например, если 'a = int затем List.find имеет желаемый тип). К сожалению, ограничения не учитываются при поиске, поэтомуList функции не могут совпадать.

Без лишних слов, вот код, который я использовал - вам нужно добавить ссылку на сборку FSharp.PowerPack.Metadata, чтобы она заработала.

open Microsoft.FSharp.Metadata
open System.Text.RegularExpressions

(* type parameters let us switch out representation if need be *)
type Tag<'ty> = | Tuple | Arr | Ground of 'ty
type Ty<'ty,'a> = Param of 'a | Complex of Tag<'ty> * Ty<'ty,'a> list

(* Gets something stable from an FSharpEntity so that we can see if two are identical *)
let rec getType (e:FSharpEntity) =
  if (e.IsAbbreviation) then
    getType e.AbbreviatedType.NamedEntity
  else
    e.ReflectionType

(* FSharpType -> Ty<System.Type,string> *)
let rec cvt (e:FSharpType) =
  if e.IsTuple then
    Complex(Tuple, e.GenericArguments |> Seq.map cvt |> List.ofSeq)
  elif e.IsFunction then
    Complex(Arr, e.GenericArguments |> Seq.map cvt |> List.ofSeq)
  elif e.IsGenericParameter then
    Param e.GenericParameter.Name
  else
    Complex(Ground(e.NamedEntity |> getType), e.GenericArguments |> Seq.map cvt |> List.ofSeq)

(* substitute type for variable within another type *)
let rec subst v t = function
| Complex(tag,l) -> Complex(tag, l |> List.map (subst v t))
| Param i when i = v -> t
| Param j -> Param j

(* get type variables used in a type *)
let rec usedVars = function
| Param i -> Set.singleton i
| Complex(tag, l) -> Set.unionMany (List.map usedVars l)

(* Find most general unifier (if any) for two types *)
let mgu t1 t2 =
  let rec mgu subs = function
  | [] -> Some subs
  | (Complex(tag1,l1),Complex(tag2,l2))::rest ->
       if tag1 <> tag2 then
         None
       else
         let rec loop r = function
         | [],[] -> mgu subs r
         | [],_ | _,[] -> None
         | x::xs, y::ys -> loop ((x,y)::r) (xs,ys)
         loop rest (l1,l2)
  | (Param i, Param j)::rest when i = j -> mgu subs rest
  | ((Param i, x) | (x, Param i))::rest ->
       if (Set.contains i (usedVars x)) then
         None (* type would be infinite when unifying *)
       else
         mgu ((i,x)::subs) (rest |> List.map (fun (t1,t2) -> (subst i x t1, subst i x t2)))
  mgu [] [t1,t2]

(* Active patterns for parsing - this is ugly... *)
let (|StartsWith|_|) r s =
  let m = Regex.Match(s, r)
  if m.Success && m.Index = 0 then
    Some(m.Value, s.Substring(m.Length))
  else None

let rec (|Any|) (|P|_|) = function
| P(x,Any (|P|_|) (l,r)) -> x::l, r
| s -> [],s

let rec (|Any1|_|) (|P|_|) = function
| P(x,Any (|P|_|) (l,r)) -> Some(x::l, r)
| _ -> None

let (|Seq|_|) (|P|_|) (|Q|_|) = function
| P(x,Q(y,r)) -> Some((x,y),r)
| _ -> None

let (|Choice|_|) (|P|_|) (|Q|_|) = function
| P(p) -> Some p
| Q(p) -> Some p
| _ -> None

let (|Delimit|_|) s (|P|_|) = function
| P(x,Any ((|Seq|_|) ((|StartsWith|_|) s) (|P|_|)) (l,r)) -> Some(x::(List.map snd l), r)
| _ -> None

let (|Delimit1|_|) s (|P|_|) = function
| P(x,StartsWith s (_,Delimit s (|P|_|) (l,r))) -> Some(x::l, r)
| _ -> None

(* Basically a BNF grammar for types *)
let rec (|TyE|_|) = function
| ArrE(p) | TupleE(p) | AtomE(p) -> Some(p)
| _ -> None
and (|ArrE|_|) = function
| Choice (|TupleE|_|) (|AtomE|_|) (dom,StartsWith "->" (_,TyE(rng,r))) -> Some(Complex(Arr,[dom;rng]), r)
| _ -> None
and (|TupleE|_|) = function
| Delimit1 @"\*" (|AtomE|_|) (l,r) -> Some(Complex(Tuple,l), r)
| _ -> None
and (|AtomE|_|) = function
| ParamE(x,r) | GroundE(x,r) | StartsWith @"\(" (_,TyE(x,StartsWith @"\)" (_,r))) -> Some(x,r)
| _ -> None
and (|ParamE|_|) = function
| StartsWith "'[a-zA-Z0-9]+" (s,r) -> Some(Param s, r)
| _ -> None
and (|GroundE|_|) = function
| StartsWith "[`.a-zA-Z0-9]+" (gnd, StartsWith "<" (_, Delimit "," (|TyE|_|) (l, StartsWith ">" (_,r)))) -> 
      let ty = FSharpAssembly.FSharpLibrary.GetEntity gnd |> getType
      Some(Complex(Ground(ty), l), r)
| StartsWith "[`.a-zA-Z0-9]+" (gnd, r) ->
      let ty = FSharpAssembly.FSharpLibrary.GetEntity gnd |> getType
      Some(Complex(Ground(ty), []), r)
| _ -> None

(* parse a string into a type *)
let parse (s:string) =
  (* remove whitespace before matching *)
  match s.Replace(" ","") with
  | TyE(ty,"") -> ty
  | _ -> failwith "Not a well-formed type"

(* an infinite stream of possible variable names - for performing renaming *)
let rec names = 
  let letters = ['a' .. 'z'] |> List.map string
  seq {
    yield! letters
    for n in names do
      for l in letters do
        yield n + l
  }

(* finds entities in the F# library with the requested signature, modulo type parameter unification *)
let find s =
  let ty = parse s
  let vars = usedVars ty
  seq {
    for e in FSharpAssembly.FSharpLibrary.Entities do
    for m in e.MembersOrValues do
      (* need try/catch to avoid error on weird types like "[]`1" *)
      match (try Some(cvt m.Type) with _ -> None) with
      | Some ty2 ->
        (* rename all type variables from the query to avoid incorrectly unifying with type variables in signatures *)
        let used = usedVars ty2
        let newVars = Seq.choose (fun v -> if Set.contains v used then None else Some(Param v)) names
        let varMap = Map.ofSeq (Seq.zip vars newVars)
        let ty = Map.fold (fun t v p -> subst v p t) ty varMap
        match mgu ty ty2 with
        | None -> ()
        | Some _ -> yield sprintf "%s.%s.%s" e.Namespace e.DisplayName m.DisplayName 
      | _ -> () }

Answer 3

Это самое последнее и самое лучшее: http://fsdn.azurewebsites.net/

Из документов: https://github.com/fsdn-projects/FSDN

Поддерживаемые подписи API

API signature                     Query example
Functions and values in modules   int -> string
Fields of records and structs     Ref<'a> => 'a
Methods and properties            'a list -> int or 'a list => int
Constructors                      string -> Uri
Names (function and method names) head : 'a list -> 'a
Active patterns                   (||) : ... -> Expr -> ?