Фильтрация списка OCaml по одному варианту

Question

Итак, у меня есть список stmt (алгебраический тип), который содержит число VarDecl в списке. Я хотел бы сократить список от stmt list до VarDecl list. Когда я использую List.filter, я могу устранить все другие типы, но я все еще остаюсь с stmt list.

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

let decls = List.fold_left 
    (fun lst st -> match st with 
     | VarDecl(vd) -> vd :: lst 
     | _ -> lst 
    ) [] stmts in 

Есть ли лучший способ выполнить фильтр и применить к варианту типа списка?

Answer 1

Предполагая, что вы имеете тип, как

type stmt = VarDecl of int | Foo of int | Bar | Fie of string 

и список STMT, Батарейки позволяет сделать

let vardecl_ints l = 
    List.filter_map (function Vardecl i -> Some i | _ -> None) l 

let foo_ints l = 
    List.filter_map (function Foo i -> Some i | _ -> None) l 

который я думаю о том, как краткое, как вы собираетесь получить. Я не делаю думаю, что вы можете создавать общие «списки-получатели» для ADT, потому что, например,

let bars l = 
    List.filter_map (function Bar -> Some Bar | _ -> None) l 

---

https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batList.mlv#L456 имеет реализацию батареи filter_map, если вы не хотите, зависимости. Функциональная версия с [] вместо Acc будет очень похожа, только делая (x :: dst) и |>List.rev в конце.

Answer 2

Трудно ответить, не видя определения вашего типа (или его упрощенной версии).

Заметим, однако, что если у вас есть такое определение:

type xyz = X | Y | Z 

Значения X, Y и Z не являются типами. Это ценности. Возможно, Vardecl тоже значение. Таким образом, вы не можете иметь список этого типа (в OCaml).

Update

Одна вещь, которую я сделал для случаев, как это использовать тип проецируемого от одного варианта вы хотите:

type xyz = X | Y of int * int | Z 

let extract_proj v l = 
    match v with 
    | X | Z -> l 
    | Y (a, b) -> (a, b) :: l 

let filter_to_y l = 
    List.fold_right extract_proj l [] 

Вот верхнего уровня сессии:

type xyz = X | Y of int * int | Z 
val extract_proj : xyz -> (int * int) list -> (int * int) list = <fun> 
val filter_to_y : xyz list -> (int * int) list = <fun> 
# filter_to_y [X; Z; Y(3,4); Z; Y(4,5)];; 
- : (int * int) list = [(3, 4); (4, 5)] 

Answer 3

Вы можете использовать GADT или полиморфные варианты, но оба имеют тенденцию повышать сложность.

Вот грубый набросок того, как вы могли бы подойти к этой проблеме с полиморфными вариантами:

type constant = [ `Int of int | `String of string ] 
type var = [ `Var of string ] 
type term = [ constant | var | `Add of term * term ] 

let rec select_vars (list : term list) : var list = 
    match list with 
    | [] -> [] 
    | (#var as v)::list -> v::select_vars list 
    | _::list -> select_vars list 

let rec select_constants (list : term list) : constant list = 
    match list with 
    | [] -> [] 
    | (#constant as k)::list -> k::select_constants list 
    | _::list -> select_constants list 

Другая возможность состоит в том, чтобы вытащить биты var из в явном тип которого вы можете иметь список :

type var = { 
    ... 
} 

type term = 
    | Int of int 
    | Var of var 

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