3

私はこの 1、2 か月間 Haskell を学んでおり、最近このコーディングの問題を解決しました。追加の課題は、余分なスペースなしで線形時間でタスクを実行することでしたが、純粋に関数的な方法で実行できるとは思わなかったので、自然に ST モナドについて知り、これは良い機会になると思いました。それについてもっと学ぶために。とにかく、ここに私が書いたコードがあります：

module FindDuplicates where

import Control.Monad (foldM)
import Control.Monad.ST
import Data.Array.ST

xs = [4,3,2,7,8,2,3,1] :: [Int]

findDuplicates :: [Int] -> ST s [Int]
findDuplicates xs = do
    arr <- newListArray (1, length xs) xs :: ST s (STArray s Int Int)

    let go :: [Int] -> Int -> ST s [Int]
        go acc i = do x <- abs <$> readArray arr i
                      y <- readArray arr x
                      if y < 0
                          then return (x:acc)
                          else do writeArray arr x (-y)
                                  return acc 

    foldM go [] [1..length xs]

アイデアは、1 ≤ a[i] ≤ n であり、各要素が最大 2 回出現するという前提条件を使用することです。しかし、コードは私に次のエラーを与えます。

FindDuplicates.hs:14:36:
    No instance for (MArray (STArray s) Int (ST s1))
      arising from a use of ‘readArray’
    In the second argument of ‘(<$>)’, namely ‘readArray arr i’
    In a stmt of a 'do' block: x <- abs <$> readArray arr i
    In the expression:
      do { x <- abs <$> readArray arr i;
           y <- readArray arr x;
           if y < 0 then
               return (x : acc)
           else
               do { writeArray arr x (- y);
                    .... } }

誰かが私を正しい方向に向けてくれることを願っています!

4

1 に答える 1

5

で注目すべき最も重要なことはNo instance for (MArray (STArray s) Int (ST s1))、2 つの異なる型変数について話していることsですs1。MArrayこれらの 2 つの型変数が同じでない限り、のインスタンスはありません。STこれは、外部的に純粋なインターフェイスで有効な方法の重要な部分です。

2 つの異なる型変数が関係しているとコンパイラが判断する理由は、型シグネチャを に付けたからgoです。そのシグネチャの型変数は、 のシグネチャのs型変数と同じではありません。これは、Haskell の型シグネチャ規則に固有の部分です。特定のシグネチャの型変数は、他のシグネチャの型変数とは無関係です。sfindDuplicates

これを修正する最も簡単な方法は、 から署名を削除することgoです。型推論により、正しい型が取得されます。

より手の込んだものにしたい場合は、ScopedTypeVariables拡張機能を使用して、署名goが型変数を囲んでいる定義と共有できるようにすることができます。

{-# LANGUAGE ScopedTypeVariables #-}
module FindDuplicates where

import Control.Monad (foldM)
import Control.Monad.ST
import Data.Array.ST

xs = [4,3,2,7,8,2,3,1] :: [Int]

findDuplicates :: forall s. [Int] -> ST s [Int]
findDuplicates xs = do
    arr <- newListArray (1, length xs) xs :: ST s (STArray s Int Int)

    let go :: [Int] -> Int -> ST s [Int]
        go acc i = do x <- abs <$> readArray arr i
                      y <- readArray arr x
                      if y < 0
                          then return (x:acc)
                          else do writeArray arr x (-y)
                                  return acc 

    foldM go [] [1..length xs]

上部のLANGUAGEプラグマは拡張機能を有効にします。拡張機能を使用するには、定義で型変数を指定する必要がありますforall。(それを忘れることは、ScopedTypeVariables仕事に失敗する最も一般的な理由です。)

の型でそれを行った後、それを定義全体のスコープfindDuplicatesに格納します。の型でs型変数を見つけると、それを新しい型変数として扱わなくなり、代わりに囲んでいるコンテキストの型と一致させます。sgos

于 2017-09-11T03:01:34.657 に答える