Iteration over string with early exit and mutable array

Learn
#1

I am new to Haskell and am attempting to write a function to determine if a string has unique characters. I have the following F# code:

// assume non-null string and all chars are in ASCII range (0-127)
let isUniqueChars (s: string) : bool =
    if String.length s <= 1 then
        true
    elif String.length s > 128 then
        false
    else
        let alphabet = Array.zeroCreate 128
        let rec loop i =
            if i < String.length s then
                let c = s.[i] |> int
                if alphabet.[c] then
                    false
                else
                    alphabet.[c] <- true
                    loop (i + 1)
            else
                true
        loop 0

I am not sure how I would write a loop with early exit in Haskell.

#2

I see no early return in your code. Here is a mostly direct translation into Haskell:

import qualified Data.IntSet as IntSet
import Data.Char (ord)

isUniqueChars :: String -> Bool
isUniqueChars s
  | length s <= 1 = True
  | length s > 128 = False
  | otherwise = loop IntSet.empty s
  where
    loop _ [] = True
    loop alphabet (c:s')
      | IntSet.member (ord c) alphabet = False
      | otherwise = loop (IntSet.insert (ord c) alphabet) s'

It is not as efficient as the original, because strings in Haskell are linked lists and I use a immutable set instead of a mutable array.

#3

Is there a way to use a mutable array in Haskell (even if an immutable set is more idiomatic)?

#4

Yes, using IO. Here I also use the faster Text type:

import qualified Data.Text as Text
import Data.Text (Text)
import qualified Data.Vector.Unboxed.Mutable as V
import Data.Char (ord)

isUniqueChars :: Text -> IO Bool
isUniqueChars s
  | Text.length s <= 1 = pure True
  | Text.length s > 128 = pure False
  | otherwise = do
    alphabet <- V.new 128
    let
      loop :: Text -> IO Bool
      loop s'
        | Text.null s' = pure True
        | otherwise = do
          let c = ord (Text.head s')
          b <- V.read alphabet c
          if b then pure False else do
            V.write alphabet c True
            loop (Text.tail s')
    loop s
#5

You can also use ST to keep the computation pure:

import qualified Data.Text as Text
import Data.Text (Text)
import qualified Data.Vector.Unboxed.Mutable as V
import Data.Char (ord)
import Control.Monad.ST (runST)

isUniqueChars :: Text -> Bool
isUniqueChars s
  | Text.length s <= 1 = True
  | Text.length s > 128 = False
  | otherwise = runST $ do
    alphabet <- V.new 128
    let
      loop s'
        | Text.null s' = pure True
        | otherwise = do
          let c = ord (Text.head s')
          b <- V.read alphabet c
          if b then pure False else do
            V.write alphabet c True
            loop (Text.tail s')
    loop s
1 Like
#6

Having roots in imperative programming, it’s taken me a while to get this one (I still forget and need to remind myself).

However, a way to think about this that has helped me: Almost anytime you reach for a loop, you are looking for some form of… Pattern Matching! (and possibly Guards).