0votos

Máquina de Turing en el sistema de tipos en Haskell

por josejuan hace 4 años

Se trabaja con cadenas en tiempo de compilación. Se concatenan, imprimen, se buscan subcadenas, ...

Animado por la elegante solución de @jmgomez al desafío Cálculo número primo con expresiones lambda, propongo realizar algún tipo de computación usando únicamente el sistema de tipos. Lógicamente, la computación debe resolverse en tiempo de compilación, nunca en tiempo de ejecución.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
{-# LANGUAGE FlexibleInstances, FlexibleContexts, OverlappingInstances #-} 
 
-- `Null` terminated strings 
data Null 
 
-- Símbolos 
data ConsA n 
data ConsB n 
 
-- Contenedor, puede quitarse, pero así queda más claro en las firmas 
data List n 
 
-- Crea una lista vacía (¡siempre en tiempo de compilación!) 
emptyList :: List Null 
emptyList = error "Not implemented" 
 
-- Inserta una `a` al inicio 
pushA :: List n -> List (ConsA n) 
pushA _ = error "Not implemented" 
 
-- Inserta una `b` al inicio 
pushB :: List n -> List (ConsB n) 
pushB _ = error "Not implemented" 
 
-- Quita cualquier símbolo del inicio 
popAny :: List (m n) -> List n 
popAny _ = error "Not implemented" 
 
-- Exige que el parámetro de entrada ¡empiece en `a`! (o `b`) 
startWithA :: List (ConsA n) -> Bool 
startWithA _ = True 
 
startWithB :: List (ConsB n) -> Bool 
startWithB _ = True 
 
-- La restricción anterior la puede usar *CUALQUER* función, ejemplos 
 
-- Hacer alguna cosa 
popAatStartPosition xs = 
  if startWithA xs 
    then popAny xs 
    else error "Imposible llegar aquí!" 
 
-- Componer nuevas restricciones 
startWithAnyAndA = startWithA . popAny 
 
 
-- Podemos buscar dentro de las secuencias, por ejemplo contenga la subsecuencia "AB" 
class MustContainsAB x 
 
instance MustContainsAB (List (ConsA (ConsB n))) -- sí, lo contiene 
instance MustContainsAB (List n) => MustContainsAB (List (ConsA n)) -- o su cola 
instance MustContainsAB (List n) => MustContainsAB (List (ConsB n)) -- o su cola 
 
-- Para imprimir valores calculados (no sólo verificados) 
class Print x where 
  showMe :: x -> IO () 
 
instance Print (List (ConsA n)) where 
  showMe _ = putStrLn "A" 
instance Print (List (ConsB n)) where 
  showMe _ = putStrLn "B" 
 
-- Un alias para lo anterior sería 
containsAB :: MustContainsAB n => n -> Bool 
containsAB _ = True 
 
-- Entonces podríamos restringir funciones como 
popStartPositionContainingAB xs = 
  if containsAB xs 
    then popAny xs 
    else error "¡Imposible llegar aquí!" 
 
 
-- Ejemplos de cadenas 
a = pushA emptyList 
b = pushB emptyList 
aa = pushA a 
ab = pushA b 
baaabaa = pushB $ pushA $ pushA $ pushA $ pushB aa 
 
{- 
 
*Main> showMe $ popStartPositionContainingAB baaabaa 
 
*Main> showMe $ popStartPositionContainingAB ab 
 
*Main> showMe $ popStartPositionContainingAB aa 
<interactive>:103:10: 
    No instance for (MustContainsAB (List Null)) 
      arising from a use of `popStartPositionContainingAB' 
    Possible fix: 
      add an instance declaration for (MustContainsAB (List Null)) 
    In the second argument of `($)', namely 
      `popStartPositionContainingAB aa' 
    In the expression: showMe $ popStartPositionContainingAB aa 
    In an equation for `it': 
        it = showMe $ popStartPositionContainingAB aa 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.