CODEWITHSUNDEEP
ocaml
Nate Brennand
Nate Brennand

Reputation: 1508

Filtering OCaml list to one variant

So I have a list of stmt (algebraic type) that contain a number of VarDecl within the list. I'd like to reduce the list from stmt list to VarDecl list. When I use List.filter I can eliminate all other types but I'm still left with a stmt list.

I found that I was able to do the filtering as well as the type change by folding, but I can't figure out how to generalize it (I need this pattern many places in the project).

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

Is there a better way to perform a filter and cast to a variant of the list type?

Upvotes: 0

Views: 1054

Answers (3)

unhammer
unhammer

Reputation: 4740

Assuming you have a type like

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

and a stmt list, Batteries lets you do

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

which I think is about as concise as you're going to get. I don't think you can make general "list-getters" for ADT's, because e.g.

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

https://github.com/ocaml-batteries-team/batteries-included/blob/d471e24/src/batList.mlv#L544 has the Batteries implementation of filter_map, if you don't want the dependency. A functional version with [] instead of dst would be quite similar, only doing (x::dst) and a |>List.rev at the end.

Upvotes: 1

gsg
gsg

Reputation: 9377

You could use GADTs or polymorphic variants, but both tend to drive up complexity.

Here's a rough sketch of how you might approach this problem with polymorphic variants:

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

Another possibility is to pull the bits of a var out into an explicit type of which you can have a list:

type var = {
  ...
}

type term =
  | Int of int
  | Var of var

This has some overhead over having the bits just be constructor args, and a var is not a term, so you will likely need to do some wrapping and unwrapping.

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

It's hard to answer without seeing your type definition (or a simplified version of it).

Note, though, that if you have this definition:

type xyz = X | Y | Z

The values X, Y, and Z aren't types. They're values. Possibly Vardecl is a value also. So you can't have a list of that type (in OCaml).

Update

One thing I have done for cases like this is to use the type projected from the one variant you want:

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 []

Here's a toplevel session:

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)]

Upvotes: 0

Related Questions