Free Palestine and Lebanon 🍉 Stop the Genocide
Haskell Logo

Programação Funcional

Questão 47: hasLoops

Voltar

Considere o seguinte tipo para representar movimentos de um robot.

data Movimento = Norte | Sul | Este | Oeste deriving Show

Defina a função hasLoops :: (Int,Int) -> [Movimento] -> Bool que, dada uma posição inicial e uma lista de movimentos (correspondentes a um percurso), verifica se o robot alguma vez volta a passar pela posição inicial ao longo do percurso correspondente. Pode usar a função posicao definida acima.

Exemplo

> hasLoops (0,0) [Norte, Norte, Este, Sul, Oeste, Sul, Este, Norte, Este]
True
> hasLoops (2,1) [Sul, Este, Sul, Oeste, Norte, Este, Sul]
False

Resolução

Clica para revelar

data Movimento = Norte | Sul | Este | Oeste deriving Show

posicao :: (Int,Int) -> [Movimento] -> (Int,Int)
posicao p [] = p
posicao (x, y) (Norte:t) = posicao (x, y + 1) t
posicao (x, y) (Sul:t) = posicao (x, y - 1) t
posicao (x, y) (Este:t) = posicao (x + 1, y) t
posicao (x, y) (Oeste:t) = posicao (x - 1, y) t

hasLoops :: (Int,Int) -> [Movimento] -> Bool
hasLoops _ [] = False
hasLoops posi movs = posi == posicao posi movs || hasLoops posi (init movs)

Explicação

Clica para revelar

A função posicao calcula a posição final do robot depois de efetuar um conjunto de movimentos.