OCaml: более высокий тип полиморфизма (абстрагирование по модулю?)

Скажем, у меня есть список вариантов:

let opts = [Some 1; None; Some 4]

Я хотел бы преобразовать их в список, например:

  • Если список содержит None, результат: None
  • В противном случае собираются различные ints.

Относительно просто написать это для этого конкретного случая (используя Core и модуль Monad):

let sequence foo =
let open Option in
let open Monad_infix in
  List.fold ~init:(return []) ~f:(fun acc x ->  
    acc >>= fun acc' -> 
    x >>= fun x' -> 
    return (x' :: acc')
    ) foo;;

Однако, как следует из названия вопроса, я бы очень хотел абстрагироваться от конструктора типа, а не специализироваться на Option. Ядро, кажется, использует функтор, чтобы дать эффект более высокого типа, но я не понимаю, как я могу написать функцию, которая будет абстрагироваться по модулю. В Scala я использую неявный контекст, требующий наличия некоторого Monad[M[_]]. Я ожидаю, что нет никакого способа неявного прохождения в модуле, но как я могу это сделать явно? Другими словами, могу ли я написать что-то, приближающееся к этому:

let sequence (module M : Monad.S) foo =
let open M in
let open M.Monad_infix in
  List.fold ~init:(return []) ~f:(fun acc x ->  
    acc >>= fun acc' -> 
    x >>= fun x' -> 
    return (x' :: acc')
    ) foo;;

Это что-то, что можно сделать с помощью модулей первого класса?

Edit: Хорошо, поэтому мне не приходило в голову попробовать использовать этот код, и он кажется, что он ближе к работе, чем я ожидал! Кажется, что синтаксис действительно действителен, но я получаю этот результат:

Error: This expression has type 'a M.t but an expression was expected of type 'a M.t
The type constructor M.t would escape its scope

Первая часть ошибки кажется сбивающей с толку, так как они совпадают, поэтому я предполагаю, что проблема связана со второй. Является ли проблема здесь, что тип возвращаемого значения, по-видимому, не определен? Я полагаю, что это зависит от модуля, который передается - это проблема? Есть ли способ исправить эту реализацию?

Ответы

Ответ 1

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

module type MonadSig = sig
  type 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
  val return : 'a -> 'a t
end

let sequence (module M : MonadSig) foo =
  let open M in
  let (>>=) = bind in
  List.fold_left (fun acc x ->  
    acc >>= fun acc' -> 
    x >>= fun x' -> 
    return (x' :: acc')
  ) (return []) foo;;

Сообщение об ошибке, которое вы получаете (путающая первая строка может следует игнорировать), что определение M.t является локальным для модуля M, и не должен сдерживать его масштабы, что он будет делать с тем, что вы пытаетесь для записи.

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

Рассмотрим следующий пример:

module type Type = sig
  type t
end

let identity (module T : Type) (x : T.t) = x

Это неправильно. Сообщения об ошибках указывают на (x : T.t) и говорят:

Error: This pattern matches values of type T.t
       but a pattern was expected which matches values of type T.t
       The type constructor T.t would escape its scope

То, что вы можете сделать, - это абстрактное задание по желаемому типу, прежде чем абстрагироваться на модуле первого класса T, чтобы больше не было выхода.

let identity (type a) (module T : Type with type t = a) (x : a) = x

Это зависит от способности явно абстрагироваться от переменной типа a. К сожалению, эта функция не была расширена до абстракции над более высокоразвитыми переменными. Вы не можете писать:

let sequence (type 'a m) (module M : MonadSig with 'a t = 'a m) (foo : 'a m list) =
  ...

Решение состоит в использовании функтора: вместо работы на уровне значения вы работаете на уровне модуля, который имеет более богатый родной язык.

module MonadOps (M : MonadSig) = struct
  open M
  let (>>=) = bind

  let sequence foo =
    List.fold_left (fun acc x ->  
      acc >>= fun acc' -> 
      x >>= fun x' -> 
      return (x' :: acc')
    ) (return []) foo;;
end

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