[haskell] 0에서 5까지의 값으로 목록을 나타내는 유형

Program / 글쓴이

0-5 값으로 목록을 표시하기 위해 유형을 정의 해야하는 연습이 있습니다. 먼저 다음과 같이 재귀 적으로 해결할 수 있다고 생각했습니다.

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

그러나 이것이 올바른 접근법이라고 생각하지 않습니다. 생각의 음식을주세요.

답변

나는 당신을 위해 당신의 운동에 대답하지 않을 것입니다-연습을 위해, 스스로 답을 알아내는 것이 낫습니다. 그러나 여기에 답을 이끌어야 할 힌트가 있습니다.

data List a = None | One a | Two a a

자, 이것을 어떻게 5 가지 요소로 확장 할 수 있는지 생각해보십시오.

답변

재귀 솔루션은 Haskell 에서 일반적이고 실제로 좋은 일이지만 요소 수를 제한하는 것은 약간 까다 롭습니다. 따라서 문제 에 대한 간단한 해결책 을 얻으려면 먼저 bradm이 제공하는 어리석지 만 작동하는 것을 고려하십시오.

재귀 솔루션을 사용하면 트릭은 “카운터”변수를 재귀에 전달한 다음 허용되는 최대 값에 도달하면 더 많은 요소를 소비하지 않도록하는 것입니다. 이것은 GADT를 사용하여 훌륭하게 수행 할 수 있습니다.

{-# LANGUAGE GADTs, DataKinds, KindSignatures, TypeInType, StandaloneDeriving #-}

import Data.Kind
import GHC.TypeLits

infixr 5 :#
data ListMax :: Nat -> Type -> Type where
  Nil :: ListMax n a
  (:#) :: a -> ListMax n a -> ListMax (n+1) a

deriving instance (Show a) => Show (ListMax n a)

그때

*Main> 0:#1:#2:#Nil :: ListMax 5 Int
0 :# (1 :# (2 :# Nil))

*Main> 0:#1:#2:#3:#4:#5:#6:#Nil :: ListMax 5 Int

<interactive>:13:16: error:
    • Couldn't match type ‘1’ with ‘0’
      Expected type: ListMax 0 Int
        Actual type: ListMax (0 + 1) Int
    • In the second argument of ‘(:#)’, namely ‘5 :# 6 :# Nil’
      In the second argument of ‘(:#)’, namely ‘4 :# 5 :# 6 :# Nil’
      In the second argument of ‘(:#)’, namely ‘3 :# 4 :# 5 :# 6 :# Nil’

답변

완벽을 기하기 위해 “못생긴”대안 접근 방식을 추가하겠습니다.

호출이 Maybe a그 값의 형식은 일종 Nothing또는 Just x일부이 x :: a.

따라서 위의 값을 해석하여 Maybe a목록이 0 개 또는 하나의 요소를 가질 수있는 “제한된 목록 유형”으로 간주 할 수 있습니다.

이제 (a, Maybe a)하나 이상의 요소를 추가하기 때문에 목록이 하나 ( (x1, Nothing)) 또는 두 ( (x1, Just x2)) 요소를 가질 수있는 “목록 유형” 입니다.

따라서 Maybe (a, Maybe a)목록에 0 ( Nothing), 1 ( Just (x1, Nothing)) 또는 2 ( (Just (x1, Just x2)) 요소 가있을 수있는 “목록 유형” 입니다.

이제 진행 방법을 이해할 수 있습니다. 이것이 사용하기 편리한 솔루션은 아니라고 다시 강조하지만 어쨌든 그것을 이해하는 것은 좋은 연습입니다.

Haskell의 몇 가지 고급 기능을 사용하여 유형 패밀리를 사용하여 위의 내용을 일반화 할 수 있습니다.

type family List (n :: Nat) (a :: Type) :: Type where
    List 0 a = ()
    List n a = Maybe (a, List (n-1) a)

답변