Chức năng này có thể được triển khai với hệ thống kiểu của Haskell không?

Question

Trong Scala, các hoạt động đặt hàng cao hơn trên các bộ sưu tập luôn trả về loại tốt nhất có thể trong ngữ cảnh. Ví dụ: trong trường hợp BitSet, nếu bạn ánh xạ ints thành ints bạn nhận được BitSet, nhưng nếu bạn ánh xạ ints thành chuỗi, bạn sẽ nhận được một số chung Set. Tương tự, nếu bạn map a Map với chức năng mang lại một cặp thì bạn sẽ nhận được số Map đổi lại. Khác bạn nhận được một đơn giản Iterable. Cả loại tĩnh và biểu diễn thời gian chạy của kết quả của bản đồ phụ thuộc vào loại kết quả của hàm được truyền cho nó.

scala> Map(2 -> 'a', 6 -> 'b') map { case (k, v) => (k + 1, v.toString) } 
res0: scala.collection.immutable.Map[Int,java.lang.String] = Map(3 -> a, 7 -> b) 

scala> Map(2 -> 'a', 6 -> 'b') map { _._1 } 
res1: scala.collection.immutable.Iterable[Int] = List(2, 6) 

scala> import collection.immutable.BitSet 
import collection.immutable.BitSet 

scala> BitSet(2, 44, 93).map(1 +) 
res3: scala.collection.immutable.BitSet = BitSet(3, 45, 94) 

scala> BitSet(2, 44, 93).map(_ + "hola") 
res4: scala.collection.immutable.Set[String] = Set(2hola, 44hola, 93hola) 

Có thể triển khai cùng chức năng trong hệ thống kiểu của Haskell không? Nếu có, làm thế nào? Một bản dịch Haskell của các ví dụ trong đoạn mã trên sẽ được nhiều đánh giá cao. :-)

Answer 1

Tôi không nghĩ rằng ví dụ đầu tiên của bạn là rất Haskell-y, vì bạn đang quá tải cùng một tên để làm hai việc rất khác nhau. Trong Haskell, khi bạn ánh xạ một hàm trên một số vùng chứa, bạn mong muốn lấy lại cùng một loại vùng chứa. Trong thực tế, điều này rất phổ biến trong Haskell rằng có một loại lớp, Functor mà gói gọn mẫu này.

Tất cả các hình thức quá tải trong Haskell đều sử dụng loại lớp và trong khi bạn có thể sử dụng chúng để đạt được điều gì đó tương tự, nó sẽ rất hữu ích và không hữu ích khi sử dụng các hàm đơn giản. .

Prelude> import qualified Data.Map as M 
Prelude Data.Map> let m = M.fromList [(2, 'a'), (6, 'b')] 
Prelude Data.Map> M.map show $ M.mapKeys (+1) m 
fromList [(3,"'a'"),(7,"'b'")] 
Prelude Data.Map> M.keys m 
[2,6] 

Tôi nghĩ ví dụ thứ hai của bạn có liên quan nhiều hơn với Haskell, vì đó là cách chọn triển khai cấu trúc dữ liệu hiệu quả nhất dựa trên loại có sẵn và tôi nghi ngờ việc này không quá khó type families, nhưng tôi không quá quen thuộc với những người đó, vì vậy tôi sẽ để người khác cố gắng trả lời phần đó.

Answer 2

Tôi rất đồng ý với Hammar, nhưng đây là một cách để làm điều đó, loại:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} 

import Prelude hiding (map) 

import qualified Data.Map as M 
import qualified Data.IntSet as I 
import qualified Data.Set as S 

type family Elem c :: * 
type instance Elem (M.Map k v) = (k, v) 
type instance Elem I.IntSet = Int 
type instance Elem (S.Set a) = a 

class Map c o where 
    type Result c o :: * 
    map :: (Elem c -> o) -> c -> Result c o 

instance Map I.IntSet Int where 
    type Result I.IntSet Int = I.IntSet 
    map = I.map 

instance Map I.IntSet String where 
    type Result I.IntSet String = S.Set String 
    map f = S.fromList . fmap f . I.toList 

instance (Ord k, Ord k1) => Map (M.Map k v) (k1, v1) where 
    type Result (M.Map k v) (k1, v1) = M.Map k1 v1 
    map f = M.fromList . fmap f . M.toList 

instance (Ord k) => Map (M.Map k v) Int where 
    type Result (M.Map k v) Int = [Int] 
    map f = fmap f . M.toList 

Đây là nó trong hành động:

*Main> map fst (M.fromList [(2::Int, 'a'), (6, 'b')]) 
[2,6] 
*Main> map (\(k, v) -> (k + 1, show v)) (M.fromList [(2, 'a'), (6, 'b')]) 
fromList [(3,"'a'"),(7,"'b'")] 
*Main> :t it 
it :: M.Map Integer [Char] 

Lý tưởng nhất là bạn muốn làm điều này :

instance (Ord k) => Map (M.Map k v) a where 
    type Result (M.Map k v) a = [a] 
    map f = fmap f . M.toList 

Nhưng trường hợp đó xung đột với cặp cho cặp. Vì vậy, không có cách nào tốt để đưa ra một ví dụ cho mọi loại khác.

Answer 3

Thêm vào hammar: Tôi nghĩ rằng ví dụ thứ hai là không thể vì nó đứng, bởi vì có chuyển đổi loại tiềm ẩn.

Bỏ qua rằng vì lợi ích của các cuộc thảo luận, làm thế nào chữ ký kiểu có thể trông giống như:

setmap :: (Set a, Set b) => a e -> (e -> f) -> b f 

Vì vậy, vâng, đây là có thể tưởng tượng, nhưng với điều kiện là người ta có thể cần phải xác định kiểu trả về.