Мое переопределение функции Haskell length не будет работать - PullRequest
Новая
       80

Мое переопределение функции Haskell length не будет работать

1 голос
/ 02 апреля 2020

Может кто-нибудь объяснить, как я могу исправить мою программу. Очень новичок в Haskell, пытался создать функцию length, которая вычисляет длину списка любого типа.

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

data List a = Nil | Cons a (List a)


len :: List a -> Int
len Nil         = 0
len (Cons _ xs) = 1 + len xs

Если я запускаю ее на len [1,2,3], я получаю ошибку: 

 • Couldn't match expected type ‘List a0’
                  with actual type ‘[Integer]’
    • In the first argument of ‘len’, namely ‘[1, 2, 3]’
      In the expression: len [1, 2, 3]
      In an equation for ‘it’: it = len [1, 2, 3]

1 Ответ

12 голосов
/ 02 апреля 2020

Определение функции правильное, но [1,2,3] не является List a объектом, это [a] (или более каноническим [] a). Список типа [1,2,3] как List Int: 

len <b>(Cons 1 (Cons 2 (Cons 3 Nil)))</b>

В качестве альтернативы, вы можете сделать List a экземпляром класса IsList, а затем использовать расширение -XOverloadedLists: 

{-# LANGUAGE <b>TypeFamilies</b> #-}

import GHC.Exts(IsList(Item, fromList, toList))

instance <b>IsList (List a)</b> where
    type Item (List a) = a
    fromList = foldr Cons Nil
    toList Nil = []
    toList (Cons x xs) = x : toList xs

Тогда мы можем использовать расширение OverloadedLists: 

$ ghci -XOverloadedLists -XTypeFamilies
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/kommusoft/.ghci
Prelude> data List a = Nil | Cons a (List a)
Prelude> import GHC.Exts(IsList(Item, fromList, toList))
Prelude GHC.Exts> :{
Prelude GHC.Exts| instance IsList (List a) where
Prelude GHC.Exts|     type Item (List a) = a
Prelude GHC.Exts|     fromList = foldr Cons Nil
Prelude GHC.Exts|     toList Nil = []
Prelude GHC.Exts|     toList (Cons x xs) = x : toList xs
Prelude GHC.Exts| :}
Prelude GHC.Exts> :{
Prelude GHC.Exts| len :: List a -> Int
Prelude GHC.Exts| len Nil         = 0
Prelude GHC.Exts| len (Cons _ xs) = 1 + len xs
Prelude GHC.Exts| :}
Prelude GHC.Exts> len [1,2,3]
3
...