Determine if a string has all unique characters: Difference between revisions

Content added Content deleted

Inline

@@ Line 859: / Line 859: @@
 =={{header|Python}}==
 ===Functional===
+Defined in terms of itertools.groupby:
+<lang python>'''Determine if a string has all unique characters'''
+from itertools import groupby
+# duplicatedCharIndices :: String -> Maybe (Char, [Int])
+def duplicatedCharIndices(s):
+    '''Just the first duplicated character, and
+       the first two indices of its occurrence,
+       of Nothing if there are no duplications.
+    '''
+    def go(xs):
+        if 1 < len(xs):
+            duplications = list(filter(lambda kv: 1 < len(kv[1]), [
+                (k, list(v)) for k, v in groupby(
+                    sorted(xs, key=lambda ix: (ix[1], ix[0])),
+                    key=snd
+                )
+            ]))
+            if duplications:
+                dup = sorted(duplications, key=lambda kv: kv[1][0])[0]
+                return Just(([x[0] for x in dup[1]], dup[0]))
+            else:
+                return Nothing()
+        else:
+            return Nothing()
+    return go(list(enumerate(s)))
+# TEST ----------------------------------------------------
+# main :: IO ()
+def main():
+    '''Test over various strings.'''
+    def showSample(s):
+        return repr(s) + ' (' + str(len(s)) + ')'
+    def showDuplicate(ixc):
+        ix, c = ixc
+        return repr(c) + (
+            ' (' + hex(ord(c)) + ') at ' + repr(ix)
+        )
+    print(
+        fTable('First duplicated character, if any:')(
+            showSample
+        )(maybe('None')(showDuplicate))(duplicatedCharIndices)([
+            '', '.', 'abcABC', 'XYZ ZYX',
+            '1234567890ABCDEFGHIJKLMN0PQRSTUVWXYZ'
+        ])
+    )
+# FORMATTING ----------------------------------------------
+# fTable :: String -> (a -> String) ->
+# (b -> String) -> (a -> b) -> [a] -> String
+def fTable(s):
+    '''Heading -> x display function -> fx display function ->
+       f -> xs -> tabular string.
+    '''
+    def go(xShow, fxShow, f, xs):
+        ys = [xShow(x) for x in xs]
+        w = max(map(len, ys))
+        return s + '\n' + '\n'.join(map(
+            lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
+            xs, ys
+        ))
+    return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
+        xShow, fxShow, f, xs
+    )
+# GENERIC -------------------------------------------------
+# Just :: a -> Maybe a
+def Just(x):
+    '''Constructor for an inhabited Maybe (option type) value.
+       Wrapper containing the result of a computation.
+    '''
+    return {'type': 'Maybe', 'Nothing': False, 'Just': x}
+# Nothing :: Maybe a
+def Nothing():
+    '''Constructor for an empty Maybe (option type) value.
+       Empty wrapper returned where a computation is not possible.
+    '''
+    return {'type': 'Maybe', 'Nothing': True}
+# maybe :: b -> (a -> b) -> Maybe a -> b
+def maybe(v):
+    '''Either the default value v, if m is Nothing,
+       or the application of f to x,
+       where m is Just(x).
+    '''
+    return lambda f: lambda m: v if (
+        None is m or m.get('Nothing')
+    ) else f(m.get('Just'))
+# snd :: (a, b) -> b
+def snd(tpl):
+    '''Second member of a pair.'''
+    return tpl[1]
+# MAIN ---
+if __name__ == '__main__':
+    main()</lang>
+{{Out}}
+<pre>First duplicated character, if any:
+                                     '' (0) -> None
+                                    '.' (1) -> None
+                               'abcABC' (6) -> None
+                              'XYZ ZYX' (7) -> 'X' (0x58) at [0, 6]
+'1234567890ABCDEFGHIJKLMN0PQRSTUVWXYZ' (36) -> '0' (0x30) at [9, 24]</pre>
+Or, as an alternative to sorting and grouping:
 <lang python>'''Determine if a string has all unique characters'''