如何用条件实现List Monad(计算表达式)？

Question

我正在尝试理解如何使用F#计算表达式,这当然让我很困惑.

以下示例对我有些意义.

type ListMonad() =
   member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = List.collect f m
   member o.Return(x) = [x]

let list = ListMonad()

let test = 
    list {
        let! x = [ 1 .. 10]
        let! y = [2 .. 2 .. 20]
        return (x,y)
    }

我的问题是,你如何为这个计算表达式添加一个条件？具体来说,如果x值严格小于y值,你将如何改变它以返回元素列表？(我们之后不要过滤掉它).

Answer 1

由于计算表达式可以参数化,您可能首先想到尝试这样的事情:

let filterAndCollect (pred : 'a -> 'b -> bool) (f : 'a -> 'b list) (m : 'a list) =
    let f' a = [ for b in f a do if pred a b then yield b ]
    List.collect f' m

type FilteringListMonad(pred) =
    member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = filterAndCollect pred f m
    member o.Return(x) = [x]

let filteredList = FilteringListMonad(fun x y -> x < y)

let test2 =
    filteredList {
        let! x = [1 .. 10]
        let! y = [2 .. 2 .. 20]
        return (x,y)
    }

但是,在(x,y)元组上出现类型错误时失败:

这个表达式应该有' int' 类型,但这里有类型' 'a * 'b'

还有两个编译器警告:在FilteringListMonad构造函数y中的x < y表达式上,有一个警告:

此构造使代码不如类型注释所指示的那样通用.类型变量'a已被约束为类型' 'b'.

而就在数1的let! x = [1 .. 10]表达,有一个警告:

此构造使代码不如类型注释所指示的那样通用.类型变量'b已被约束为类型' int'.

因此,在这两个约束之间,计算表达式(a 'b list)的返回类型已被约束为int list,但您的表达式返回的是int * int list.在考虑了类型约束之后,您可能会得出结论,这是不可行的.但有一种方法可以让它发挥作用.关键是要意识到,作为'b计算表达式输出的类型,在本例中,实际上是元组 int * int,所以你重写谓词函数实际只是采用那种'b类型,然后一切正常:

let filterAndCollect (pred : 'b -> bool) (f : 'a -> 'b list) (m : 'a list) =
    let f' a = [ for b in f a do if pred b then yield b ]
    List.collect f' m

type FilteringListMonad(pred) =
    member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = filterAndCollect pred f m
    member o.Return(x) = [x]

let filteredList = FilteringListMonad(fun (x:int,y:int) -> x < y)

let test2 =
    filteredList {
        let! x = [ 1 .. 10]
        let! y = [2 .. 2 .. 20]
        return (x,y)
    }

请注意,我还必须指定谓词函数输入的类型.没有它,F#将它们概括为"任何实现的类型System.IComparable,但我传入的是ints,它们是值类型,因此不实现任何接口.这导致了错误

该表达式应该具有类型' System.IComparable',但这里有类型' int'.

但是,将这两个参数声明为谓词int.

Answer 2

OP已经接受了答案,我将提供一种不同的方法,可能有助于理解F#中的计算表达式

一个可以与有用延伸计算表达式ReturnFrom和Zero像这样:

type ListMonad() =
   member o.Bind        (m, f)  = List.collect f m
   member o.Return      x       = [x]
   member o.ReturnFrom  l       = l : _ list
   member o.Zero        ()      = []

let listM = ListMonad()

ReturnFrom允许我们返回空列表return! [],因此可以进行过滤.Zero这是一个简写,如果使用else未定义分支Zero.

这允许我们像这样过滤:

let test = 
  listM {
    let! x = [ 1 .. 10]
    let! y = [2 .. 2 .. 20]
    if x % y = 0 then
      return (x,y)
//  By defining .Zero F# implicitly adds else branch if not defined
//  else
//    return! []
  }

F#会将计算扩展为大致如下:

let testEq = 
  [ 1 .. 10] 
  |> List.collect 
      (fun x -> 
        [2 .. 2 .. 20] 
        |> List.collect (fun y -> if x % y = 0 then [x,y] else [])
      )